IOI’94 – Day 2
|-------| |-------| |-------|
| | | | | | |
|---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. |
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).
SOLUTION
1.广度优先搜索
这道题叙述感觉很像最少步数问题，因此我第一个想到的就是BFS。开始的思路是这样的：搜索树为一个”九叉树”，从根节点到每一个节点的路径代表一个操作序列。每一个节点扩展出9个节点。当在某一深度找到可行解时，则完成该深度所有节点的检查，取其中操作序列连接的数字最小的为答案。
但是很明显，这个算法在时间复杂度和空间复杂度上都不可接受。
我们又发现：1.任何一个操作执行4次就等于没有执行；2.同一个操作序列，各个操作的顺序改变不影响整个序列的操作效果。
根据以上两点，我们可以进行如下改进：1.任何操作不超过3次；2.为了避免同一操作序列由于顺序不同造成的节点重复，我们每次扩展节点时，都只对操作号大于当前操作号的操作进行尝试。
这样，我们就得到了一棵小得多的搜索树。这棵树的最大深度为3*9=27，节点数为4的9次方即262144，根节点到任意节点路径所代表的操作序列都是不重复的。（要知道原来的搜索树有无限的深度和节点数，且充满了重复）。而且我们发现，由于节点的生成方式，我们通过bfs找到的第一个可行解必然就是最优解。
/*
ID:tom.tun1
PROG:clocks
LANG:C++
*/
#include <iostream>
#include <fstream>
#include <cstring>
using namespace std;
ifstream fin("clocks.in");
ofstream fout("clocks.out");
struct
{
char Time[9];//九个钟表的状态：0,3,6,9
char depth;//当前节点的深度
char num[28];//记录到达该节点的各个操作编号
char operate_times[9 + 1];//operate_times[i]的值为已经进行i操作的次数
char operation;//记录直接得到本节点的操作
}Clocks[270000];
const char operate[9 + 1][6] =
{
/*每个操作影响的钟表号，每个操作的序列以-1结尾*/
0, 0, 0, 0, 0, 0, 0, 1, 3, 4, -1, 0, 0, 1, 2, -1, 0, 0, 1, 2, 4, 5, -1, 0,
0, 3, 6, -1, 0, 0, 1, 3, 4, 5, 7, -1, 2, 5, 8, -1, 0, 0, 3, 4, 6, 7, -1, 0,
6, 7, 8, -1, 0, 0, 4, 5, 7, 8, -1, 0
};
int
main()
{
/*输入及初始化*/
for (int i = 0,c; i < 9; i++)
{
fin >> c;
if (c == 12)
c = 0;
Clocks[0].Time[i] = c + '0';
}
Clocks[0].depth = 0;
Clocks[0].operation = 1;
memset(Clocks[0].operate_times, 0, sizeof(Clocks[0].operate_times));
/*BFS*/
int head = 0, tail = 1;/*首尾指针*/
bool flag = true;
while (flag && head < tail)
{
for (int i = Clocks[head].operation;
i <= 9;
i++)/*生成的i对应操作的编号*/
{
/*如果某操作执行超过3次则取消本次循环*/
if (Clocks[head].operate_times[i] + 1 > 3)
continue;
/*产生节点*/
strcpy(Clocks[tail].Time, Clocks[head].Time);/*Time[9]部份*/
for (int j = 0; operate[i][j] != -1; j++)
{
int n = operate[i][j];
if (Clocks[head].Time[n] == '9')
Clocks[tail].Time[n] = '0';
else
Clocks[tail].Time[n] = Clocks[head].Time[n] + 3;
}
Clocks[tail].depth = Clocks[head].depth + 1;/*depth部份*/
strcpy(Clocks[tail].num, Clocks[head].num);/*num[]部份*/
Clocks[tail].num[Clocks[head].depth] = i + '0';
/*operate_times[]部份*/
memcpy(Clocks[tail].operate_times, Clocks[head].operate_times,
sizeof(Clocks[0].operate_times));
Clocks[tail].operate_times[i]++;
Clocks[tail].operation = i;/*operation部份*/
/*节点产生完毕*/
/*判断是否达到目标节点*/
flag = false;
for (int j = 0; j < 9; j++)
if (Clocks[tail].Time[j] != '0')
{
flag = true;
break;
}
if (!flag)
break;
tail++;
}
head++;
}
/*输出答案*/
for (int i = 0; i < strlen(Clocks[tail].num); i++)
{
if (i == strlen(Clocks[tail].num) - 1)
fout << Clocks[tail].num[i] << endl;
else
fout << Clocks[tail].num[i] << ' ';
}
//system("pause");
return 0;
}
2.深度优先搜索
当我们得到了上面那棵搜索树后，我们发现由于深度和节点数都不大，DFS是完全可行的，而且更易于编写，省去了节省内存空间的麻烦。如同ghost所说，此题穷举才是正解。我们搜索过程中不断更新得到的最优解，当整棵树都遍历后就输出答案。可见此算法耗时相当稳定。我这里根据深度进行了小小的剪枝，完美AC。有牛说其实完全可以不要任何剪枝的，时间就可以稳定在0.3s。
源码如下：
/*
ID:tom.tun1
PROG:clocks
LANG:C++
*/
#include <iostream>
#include <fstream>
using namespace std;
ifstream fin("clocks.in");
ofstream fout("clocks.out");
struct Clocks
{
char Time[9];//九个钟表的状态：0,3,6,9
int depth;//当前节点的深度
char num[28];//记录到达该节点的各个操作编号
int operate_times[9 + 1];//operate_times[i]的值为已经进行i操作的次数
}FirstClock;
const char operate[9 + 1][6] =
{
/*每个操作影响的钟表号，每个操作的序列以-1结尾*/
0, 0, 0, 0, 0, 0, 0, 1, 3, 4, -1, 0, 0, 1, 2, -1, 0, 0, 1, 2, 4, 5, -1, 0,
0, 3, 6, -1, 0, 0, 1, 3, 4, 5, 7, -1, 2, 5, 8, -1, 0, 0, 3, 4, 6, 7, -1, 0,
6, 7, 8, -1, 0, 0, 4, 5, 7, 8, -1, 0
};
char min_num[28], min_depth = 30;
void
search(struct Clocks Clock, int i)//DFS递归函数，Clock为当前节点，i操作编?
{
/*节点产生*/
struct Clocks NextClock;
/*depth部分*/
NextClock.depth = Clock.depth + 1;
if (NextClock.depth > min_depth)
return;
/*num部分*/
strcpy(NextClock.num, Clock.num);
NextClock.num[NextClock.depth - 1] = i + '0';
/*Time[9]部分*/
strcpy(NextClock.Time, Clock.Time);
for (int j = 0; operate[i][j] != -1; j++)
{
int n = operate[i][j];
if (Clock.Time[n] == '9')
NextClock.Time[n] = '0';
else
NextClock.Time[n] = Clock.Time[n] + 3;
}
/*operate_times部分*/
memcpy(NextClock.operate_times, Clock.operate_times,
sizeof(Clock.operate_times));
if (++NextClock.operate_times[i] > 3)
return;
/*检查是否为目标节点*/
if (strcmp(NextClock.Time, "000000000") == 0)
{
/*更新min_depth和min_num的值*/
if (NextClock.depth < min_depth)
{
strcpy(min_num, NextClock.num);
min_depth = NextClock.depth;
return;
}
}
/*递归*/
for (int j = i; j <= 9; j++)
search(NextClock, j);
}
int
main()
{
/*输入及初始化*/
for (int i = 0,c; i < 9; i++)
{
fin >> c;
if (c == 12)
c = 0;
FirstClock.Time[i] = c + '0';
}
FirstClock.depth = 0;
memset(FirstClock.operate_times, 0, sizeof(FirstClock.operate_times));
/*DFS*/
for (int i = 1; i <= 9; i++)
search(FirstClock, i);
/*输出答案*/
for (int i = 0; i < min_depth; i++)
{
if (i == min_depth - 1)
fout << min_num[i] << endl;
else
fout << min_num[i] << ' ';
}
return 0;
}
3.特殊方法
上面两种方法只是常规的，不足为奇。下面贴出我翻译自USACO官方Analysis的两种方法。非常精彩。
Lucian Boca提交了一种常数时间的解法
你可以预先计算一个如下的矩阵：
a[i][0],a[i][1],….,a[i][8]是“仅仅”将第i个钟表（0<=i<=8，共有9个钟表：0=A, 1=B, … 8=I）顺时针转动90度所必须的操作1、2、3…9的执行次数。这样你就得到了一个矩阵：
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} };这意味着仅仅将钟表0（钟表A）顺时针转动90度，你必须执行{3,3,3,3,3,2,3,2,0}，即操作1执行3次，操作2执行3次，…，操作8执行2次，操作9执行0次，等等。
仅仅将钟表8（钟表I）顺时针转动90度，你必须执行{0,2,3,2,3,3,3,3,3}：操作1执行0次，操作2执行2次…操作9执行3次…
没错！你可以在一个数组v[9]里记录每一种必须执行操作的次数，答案就是它取4的模（任何一种操作执行5次与执行1次效果一样）。源码：
#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; }这是来自Sopot Cela的另一种解法——没有循环，常数时间。但这个实在是极端的复杂：在比赛的环境下想要写对这样一个程序将是一种极限挑战。
program clocks; const INV : array[3..12] of byte =(1, 0, 0, 2, 0, 0, 3, 0, 0, 0); var inp, out: text; a, b, c, d, e, f, g, h, i: integer; ax, bx, cx, dx, ex, fx, gx, hx, ix,l: integer; t,an: array[1..9] of integer; begin assign (inp, 'clocks.in'); reset (inp); readln(inp, ax, bx, cx); readln(inp, dx, ex, fx); readln(inp, gx, hx, ix); a:=inv[ax]; b:=inv[bx]; c:=inv[cx]; d:=inv[dx]; e:=inv[ex]; f:=inv[fx]; g:=inv[gx]; h:=inv[hx]; i:=inv[ix]; t[1] := (8+a+2*b+c+2*d+2*e-f+g-h) mod 4; t[2] := (a+b+c+d+e+f+2*g+ 2*i) mod 4; t[3] := (8+ a+2*b+ c -d+2*e+2*f -h+ i) mod 4; t[4] := ( a+ b+2*c+ d+ e+ g+ h+2*i) mod 4; t[5] := (4+ a+2*b+ c+2*d -e+2*f+ g+2*h+ i) mod 4; t[6] := ( 2*a+ b+ c+ e+ f+2*g+ h+ i) mod 4; t[7] := (8+ a -b+ 2*d+2*e -f+ g+2*h+ i) mod 4; t[8] := ( 2*a+ 2*c+ d+ e+ f+ g+ h+ i) mod 4; t[9] := (8 -b+ c -d+2*e+2*f+ g+2*h+ i) mod 4; assign(out, 'clocks.out'); rewrite(out); for a := 1 to 9 do for b := 1 to t[a] do Begin inc(l); an[l]:=a; end; for a:=1 to l-1 do write(out,an[a],' '); write(out,an[l]); writeln(out); close(out) end.
可能你对下面的文章也感兴趣：
