Consider nine clocks arranged in a 3x3 array thusly:
|-------| |-------| |-------|
| | | | | | |
|---O | |---O | | O |
| | | | | |
|-------| |-------| |-------|
A B C
|-------| |-------| |-------|
| | | | | |
| O | | O | | O |
| | | | | | | | |
|-------| |-------| |-------|
D E F
|-------| |-------| |-------|
| | | | | |
| O | | O---| | O |
| | | | | | | |
|-------| |-------| |-------|
G H I
The goal is to find a minimal sequence of moves to return all the dials to 12 o'clock. Nine different ways to turn the dials on the clocks are supplied via a table below; each way is called a move. Select for each move a number 1 through 9 which will cause the dials of the affected clocks (see next table) to be turned 90 degrees clockwise.
|
Move |
Affected clocks |
|
1 |
ABDE |
|
2 |
ABC |
|
3 |
BCEF |
|
4 |
ADG |
|
5 |
BDEFH |
|
6 |
CFI |
|
7 |
DEGH |
|
8 |
GHI |
|
9 |
EFHI |
Example
Each number represents a time accoring to following table:
9 9 12 9 12 12 9 12 12 12 12 12 12 12 12
6 6 6 5 -> 9 9 9 8-> 9 9 9 4 -> 12 9 9 9-> 12 12 12
6 3 6 6 6 6 9 9 9 12 9 9 12 12 12
[But this might or might not be the `correct' answer; see below.]
PROGRAM NAME: clocks
INPUT FORMAT
|
Lines 1-3: |
Three lines of three space-separated numbers; each number represents the start time of one clock, 3, 6, 9, or 12. The ordering of the numbers corresponds to the first example above. |
SAMPLE INPUT (file clocks.in)
9 9 12
6 6 6
6 3 6
OUTPUT FORMAT
A single line that contains a space separated list of the shortest sequence of moves (designated by numbers) which returns all the clocks to 12:00. If there is more than one solution, print the one which gives the lowest number when the moves are concatenated (e.g., 5 2 4 6 < 9 3 1 1).
SAMPLE OUTPUT (file clocks.out)
4 5 8 9
这个问题要求用最少的步骤把所有的表盘都调整到12点，所能使用的操作集合是给定的。首先我们也许会担心这九种操作是否总能给出一个解决方案，答案是肯定的，因为对于任意表盘，都有一个操作序列能使表针不多不少顺时针转动90度同时其他表盘最终回到原状态（通过应用我们的算法可以预计算出这些操作序列，实际上这些序列的计算只是原问题的特例）。如此以来，通过累积这些序列的操作，我们肯定能得到一个问题的解（这正是USACO题解中给出的一种方法）。
然后我们注意到所有操作最多可以做3次（如果一种操作做4次，等价于没有做任何操作），而且操作顺序对结果没有影响（因为操作的效果是累加的）。这样以来所有可能的操作序列有4^9=262144个，这个数量级完全可以暴力破解（USACO对程序的限制是：运行时间<1s，内存<14M，栈<1M）。
如此一来通过DFS枚举所有情况是完全可行的。但是由于这个问题实质上属于求“最短路径”（这里路径就是操作序列），我选择了BFS以保证得到的第一个解就是最优解（DFS因为是深度优先，不遵循路径长度的顺序进行搜索，第一个解一般不是最优解，所以需要遍历所有情况，这消耗了不必要的时间），当然这需要对搜索的顺序做一定的安排：按非递减顺序遍历，每种操作最多三次。
BFS看似是个不错的选择，但是最多262144个搜索节点数让人头疼，为此我MLE（Memory Limit Exceeded）了一次。之后我想到了使用循环队列【1】。
【1】循环队列开多大？找到搜索树中节点数之和最多的相邻两层，如果这个节点数之和是n，那么循环队列开到n+1应该就可以了。假设队列长度为n+1但是搜索过程中队尾循环回来覆盖了队头，这说明队头节点和队尾节点之间有n个节点，这与相邻两层节点数之和最多为n相矛盾（注意到BFS时队头节点永远在队尾节点的上一层）。
但是对于这道题，我的搜索树形状很奇特，这给估算n值带来了很大麻烦，在尝试之后我取了n=50000并且AC。这显然是BFS在解决这个问题时最大的坏处。
作为一个对空间的优化，实际上可以使用位运算，这样可以用一个整数的比特位表示所有表盘的状态，这让它既省空间又省时间。但我没有尝试。
我的程序代码：
/*
ID: *******
LANG: C
TASK: clocks
*/
#include<stdio.h>
FILE *fin,*fout;
typedef struct{
int clo[9];//表盘状态
int beg;//第一个要尝试的操作的编号
int count[9];//每种操作的次数
int memo[27];//操作序列
int pMemo;
}CL;//搜索树节点的定义
CL queue[50001];
int tailQue=-1;
int headQue=-1;
int move[9][9]={
{3,3,0,3,3,0,0,0,0},
{3,3,3,0,0,0,0,0,0},
{0,3,3,0,3,3,0,0,0},
{3,0,0,3,0,0,3,0,0},
{0,3,0,3,3,3,0,3,0},
{0,0,3,0,0,3,0,0,3},
{0,0,0,3,3,0,3,3,0},
{0,0,0,0,0,0,3,3,3},
{0,0,0,0,3,3,0,3,3}
};
int testOutput(int po){
int isAnswer=1;
int i;
for(i=0;i<9;i++){
if(queue[po].clo[i]!=12){
isAnswer=0;
break;
}
}
if(isAnswer==1&&queue[po].pMemo>=0){
fout=fopen("clocks.out","w");
fprintf(fout,"%d",queue[po].memo[0]+1);
for(i=1;i<=queue[po].pMemo;i++){
fprintf(fout," %d",queue[po].memo[i]+1);
}
fprintf(fout,"\n");
}
return isAnswer;
}
int main(){
fin=fopen("clocks.in","r");
int i;
headQue=0;
tailQue=1;
for(i=0;i<9;i++){
fscanf(fin,"%d",&queue[headQue].clo[i]);
queue[headQue].count[i]=0;
}
queue[headQue].pMemo=-1;
queue[headQue].beg=0;
while(headQue!=tailQue){//开始BFS
if(testOutput(headQue)==1)break;
for(i=queue[headQue].beg;i<9;i++){
if(queue[headQue].count[i]>=3)continue;
int j;
for(j=0;j<9;j++){
queue[tailQue].clo[j]=queue[headQue].clo[j]+move[i][j];
if(queue[tailQue].clo[j]>12)
queue[tailQue].clo[j]-=12;
queue[tailQue].count[j]=queue[headQue].count[j];
}
for(j=0;j<=queue[headQue].pMemo;j++)
queue[tailQue].memo[j]=queue[headQue].memo[j];
queue[tailQue].count[i]++;
queue[tailQue].pMemo=queue[headQue].pMemo+1;
queue[tailQue].memo[queue[tailQue].pMemo]=i;
queue[tailQue].beg=i;
//printf("tail:%d\n",tailQue);
tailQue++;
if(tailQue>50000)tailQue=0;
}
headQue++;
if(headQue>50000)headQue=0;
}
return 0;
}
USACO题解的第一种方法是DFS：
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>
#include <ctype.h>
#define INF 60000 /* bigger than longest possible path */
char *movestr[] = { "abde", "abc", "bcef", "adg", "bdefh", "cfi", "degh",
"ghi", "efhi" };
int movedist[9][9];
int clock[9];
int bestmove[9];
int nbestmove;
/* translate move strings into array "movedist" of which clocks change on each move */
void
mkmove(void)
{
int i;
char *p;
for(i=0; i<9; i++)
for(p=movestr[i]; *p; p++)
movedist[i][*p-'a'] = 3;
}
/* apply some number of each move from k to 9 */
/* move contains the number of times each move is applied */
void
solve(int *move, int k)
{
int i, j, n, rep;
if(k == 9) {
for(j=0; j<9; j++)
if(clock[j]%12 != 0)
return;
/* we have a successful sequence of moves */
n = 0;
for(j=0; j<9; j++)
n += move[j];
if(nbestmove == 0 || n < nbestmove) {
nbestmove = n;
for(j=0; j<9; j++)
bestmove[j] = move[j];
}
return;
}
/*
* the for loop counts down so we
* generate smaller numbers first by
* trying more of small numbered
* moves before we try less of them.
*/
for(rep=3; rep>=0; rep--) {
/* apply move k rep times */
for(i=0; i<rep; i++)
for(j=0; j<9; j++)
clock[j] += movedist[k][j];
move[k] = rep;
solve(move, k+1);
/* undo move */
for(i=0; i<rep; i++)
for(j=0; j<9; j++)
clock[j] -= movedist[k][j];
}
}
void
main(void)
{
FILE *fin, *fout;
int i, j, move[9];
char *sep;
fin = fopen("clocks.in", "r");
fout = fopen("clocks.out", "w");
assert(fin != NULL && fout != NULL);
mkmove();
for(i=0; i<9; i++)
fscanf(fin, "%d", &clock[i]);
solve(move, 0);
sep = "";
for(i=0; i<9; i++) {
for(j=0; j<bestmove[i]; j++) {
fprintf(fout, "%s%d", sep, i+1);
sep = " ";
}
}
fprintf(fout, "\n");
exit(0);
}
第二种方法很独特，正如文章开头提到的“对于任意表盘，都有一个操作序列能使表针不多不少顺时针转动90度同时其他表盘最终回到原状态”。这是USACO的原文：
You can precalculate a matrix a as following:
a[i][0],a[i][1],....,a[i][8] is the number of moves '1','2','3',...'9' necessarly to move ONLY clock i (where 0 < i <= 8 - there are 9 clocks: 0=A, 1=B, ... 8=I) 90 degrees clockwise. So, you have the matrix:
int a[9][9]= { {3,3,3,3,3,2,3,2,0},
{2,3,2,3,2,3,1,0,1},
{3,3,3,2,3,3,0,2,3},
{2,3,1,3,2,0,2,3,1},
{2,3,2,3,1,3,2,3,2},
{1,3,2,0,2,3,1,3,2},
{3,2,0,3,3,2,3,3,3},
{1,0,1,3,2,3,2,3,2},
{0,2,3,2,3,3,3,3,3} };
That means: to move ONLY the clock 0 (clock A) 90 degrees clockwise you have to do {3,3,3,3,3,2,3,2,0}, 3 moves of type 1, three moves of type 2, ..., 2 moves of type 8, 0 moves of type 9, etc.
To move ONLY the clock 8 (clock I), you have to do the moves {0,2,3,2,3,3,3,3,3}: 0 moves of type 1, 2 moves of type 2... 3 moves of type 9....
That's it! You count in a vector v[9] how many moves of each type you have to do, and the results will be modulo 4 (%4 - 5 moves of any type have the same effect 1 move has).
代码：
#include <stdio.h>
int a[9][9]= { {3,3,3,3,3,2,3,2,0},
{2,3,2,3,2,3,1,0,1},
{3,3,3,2,3,3,0,2,3},
{2,3,1,3,2,0,2,3,1},
{2,3,2,3,1,3,2,3,2},
{1,3,2,0,2,3,1,3,2},
{3,2,0,3,3,2,3,3,3},
{1,0,1,3,2,3,2,3,2},
{0,2,3,2,3,3,3,3,3} };
int v[9];
int main() {
int i,j,k;
freopen("clocks.in","r",stdin);
for (i=0; i<9; i++) {
scanf("%d",&k);
for(j=0; j<9; j++)
v[j]=(v[j]+(4-k/3)*a[i][j])%4;
}
fclose(stdin);
k=0;
freopen("clocks.out","w",stdout);
for (i=0; i<9; i++)
for (j=0; j<v[i]; j++)
if (!k) { printf("%d",i+1); k=1; }
else printf(" %d",i+1);
printf("\n");
fclose(stdout);
return 0;
}
方法就是预先计算出所有这些序列，然后针对具体问题简单地叠加这些操作序列，如果一种操作超过了4次，将操作次数模4取余。这种方法可以在O(1)时间内解决问题。问题是这种方法能够总是得到最优解吗？
我认为这种方法成立的一个重要前提是 9种基本操作中任意一种不能由其余操作的组合来等效！
这样一来，操作2（ABC）等于a[0]+a[1]+a[2]（a[i]表示一个向量），也就是说(a[0]+a[1]+a[2])mod 4 == {0,1,0,0,0,0,0,0,0} （参照原文中的int a[9][9]），也就是说a矩阵中各种操作的叠加不仅和操作2等效，而且实际上就是操作2。相反，如果这个重要前提不成立，例如操作2可以由操作1和操作3叠加得到，那么a[0]+a[1]+a[2]有可能等于{1,0,1,0,0,0,0,0,0} 这样由此算法得到的解不一定是最优解（一个操作变成了两个操作，操作步骤增加了）。
如果这个前提成立，那么这个算法肯定是安全的，当然这只是一个充分条件，至于其必要性我没能证明。不过从另一角度考虑，一个“九维”的表盘组，表盘之间没有相关性，如果操作2可以由操作1和3叠加的话，实际上我们只有8种操作方式，这显然是不够的，对于一些情况它甚至不能成功的将所有表盘调到12点！
那么这个安全性如何被保证呢？当这个前提成立时，我们的搜索算法和这个常数时间算法是等价的。因为9种操作的每一种都和a矩阵中的某操作序列唯一等价。当你被告知a矩阵向量的某种组合可以组合出最优解，而且把重复4次的向量消去后你只有唯一一种组合方式，那么这个组合不是最优解又能是什么呢？
PS. 本文所有推理都是意淫，事实上本人没有什么数学造诣以至于不能给出形式化的证明。
.gif)
