d730. 升旗典礼 ——加强版
http://zerojudge.tw/ShowProblem?problemid=d730
內容 ：
幼稚園老師帶小朋友最頭痛的就是在昇旗典禮的時候。
小朋友在典禮中很容易亂動，要令他們都朝向旗子所在的方向卻是困難的。
現在簡化問題。總共有9個小朋友，小朋友面朝的方向只有北東南西四個方向。
我們定義0為北方, 1為東方, 2為南方, 3為西方, 從北方開始, 順時針方向轉一圈為0 -> 1 -> 2 -> 3 -> 0。
老師則使用9種口令來同時讓數位小朋友順時針轉90度
口令 那幾個小朋友順時針轉90度(數字代表第幾個)
1 1, 2, 4, 5
2 1, 2, 3
3 2, 3, 5, 6
4 1, 4, 7
5 2, 4, 5, 6, 8
6 3, 6, 9
7 4, 5, 7, 8
8 7, 8, 9
9 5, 6, 8, 9
例如：如果原本第1, 2, 4, 5個小朋友面朝北方(0)，老師喊口令1，第1, 2, 4, 5個小朋友會變成面朝東方(1)
旗子永遠在北方，而老師要使用口令讓所有小朋友都朝向北方。口令使用次數不限，請你求出其一連串的口令所形成的最短序列，並列印出來。
輸入說明
：
输入包含许多组测资。
测资第一行有一个整数，代表共有几组测资。
每组测资为1行，这一行里有9个整数，范围0到3，代表9位小朋友原本所朝的方向。
这9个整数的每个整数之间以一个空白字元隔开。
輸出說明
：
输出为口令所形成的最短序列，每组输出为1行，其口令序列中的每个口令间以一个空白字元隔开。
如果有2组(含)以上的最短序列，请输出字典排序最小者。
例如：1 1 3 4 5 和1 2 3 4 5 两序列，要输出1 1 3 4 5。
範例輸入 ：
1 2 3 1 1 1 3 0 0 0
範例輸出 ：
1 1 2 2 2 4 8 8 8 9
提示
：
这题是 d298: 升旗典礼 加强版。
测试数据可能会非常庞大，所以你的程序一定要跑得非常快。//一共大约100000笔
为这题抓狂吧！
出處
：
/**********************************************************************************/
/* Problem: d730 "升旗典礼 ——加强版" from IOI'94 The Clocks 再次加强*/
/* Language: C */
/* Result: AC (352ms, 3072KB) on ZeroJudge */
/* Author: morris1028 at 2011-05-30 22:59:54 */
/**********************************************************************************/
#include<stdio.h>
char mark[270000] = {}, ans[270000], best[270000], dir[4] = {3,0,1,2}, dirp[4] = {-3,1,1,1};
int next[270000] = {};
int s4[10] = {1}, Queue[270000];
char Map[10][7] = {{},
{1,2,4,5,0},
{1,2,3,0},
{2,3,5,6,0},
{1,4,7,0},
{2,4,5,6,8,0},
{3,6,9,0},
{4,5,7,8,0},
{7,8,9,0},
{5,6,8,9,0}
};
void Change(int N, int flag, char C[]) {
while(N) {
C[flag] = N%4, N /= 4, flag++;
}
}
void Build() {
int a, b, c, qt = 0, t, p;
Queue[qt++] = 0, best[0] = 0, ans[0] = 10, mark[0] = 1;
for(a = 0; a < qt; a++) {
t = Queue[a], p;
char C[10] = {};
Change(t, 0, C);
for(b = 1; b < 10; b++) {
for(c = 0, p = t; Map[b][c]; c++) {
p -= s4[Map[b][c]-1] * dirp[C[Map[b][c]-1]];
} /*c*/
if(mark[p] == 0) {
mark[p] = 1,Queue[qt++] = p;
next[p] = t, best[p] = best[t] + 1, ans[p] = b+'0';
}
else {
if(best[p] > best[t]+1) {
Queue[qt++] = p;
next[p] = t, best[p] = best[t] + 1, ans[p] = b;
}
}
} /*b*/
} /*a*/
}
void Print(int now) {
if(now) {
Print(next[now]);
putchar(ans[now]), putchar(' ');
}
}
main() {
int t, a, s, x;
for(a = 1; a < 10; a++)
s4[a] = s4[a-1] * 4;
Build();
scanf("%d", &t);
while(t--) {
for(a = 0, s = 0; a < 9; a++) {
scanf("%d", &x);
s += x * s4[a];
}
Print(s), puts("");
}
return 0;
}