呵呵，让你破费了。先把原题复制过来便于讲解。
2x3=6个方格中放入ABCDE五个字母，右下角的那个格空着。如图【1.jpg】所示。
和空格子相邻的格子中的字母可以移动到空格中，比如，图中的C和E就可以移动，移动后的局面分别是：
A B
D E C
A B C
D E
为了表示方便，我们把6个格子中字母配置用一个串表示出来，比如上边的两种局面分别表示为：
AB*DEC
ABCD*E
题目的要求是：请编写程序，由用户输入若干表示局面的串，程序通过计算，输出是否能通过对初始状态经过若干次移动到达该状态。可以实现输出1,否则输出0。初始状态为：ABCDE*
用户输入的格式是：先是一个整数n，表示接下来有n行状态。程序输出也应该是n行1或0
例如，用户输入：
3
ABCDE*
AB*DEC
CAED*B
则程序应该输出：
1
1
0
这个题目用图论来分析是很简单的。先说说它的图论建模方案。
将每一种局面（其实我更喜欢叫做状态）看成一个点。如果局面A通过一次移动（只移动一个格子）可以转换成局面B，那么可以看成点A到点B之间有一条连线。
如果A经一次移动可以转换成B，那么B经一次移动也可以转换成A。所以这条连线是没有方向的，也就是说我们建的图是无向图。
那么题目要求的“是否能通过对初始状态经过若干次移动到达该状态”，既是在图中初始点与“该”点是否连通。
关于连通性的判断。如果点A与点B连通，则这们构成一个相对于A的连通点集（设这个点集为S，它是图中所有点的一个子集）。如果点C与S中的任意一点连通，则它也与A连通。点C也可以加入点集S。事实上对于无向图，S中的任意两点都是连通的，它叫做连通图。
显然题目中的状态包括这2 X 3的格子的所有可能状态。这些状态中有一些与初始状态是连通的，有一些则不连通。如果我们找出所有与初始状态连通的状态，则对于题目给出的状态，我们要需要判断一下它是否在这些连通的状态中即可。
理论分析就到这里吧，下面开始将分析转变成编码。
我们需要用一个结点表示一种状态。至于怎么表示则根据设计者的思维习惯不同而不同。
有人可能会用一个结构来表示，里面包含一个2 X 3的字符数组。
这当然可以。优点是直观，缺点是结点的尺寸有点大。
而我的习惯是用位来表示。每一个格子只有6种状态（A、B、C、D、E、*）。用3个二进制位即可表示一个格子，其值 0表示“*”，1~5表示“A”~“E”。
这样，2 X 3个格子一共用18位即可表示。为了方便实际我用一个32位整型变量来表示一种格子局面，每个格子使用了4位，一共使用了低24位。
由于还有多余的位，我又用了4位来表示空格（即*）所在的位置（第24至27位）。这么做是为了提高效率方便操作（不必每次找空格在哪一位了）。
点表示完了，那么结点之间的连接关系如何表示？
可以用邻接表、邻接矩阵，或给结点添加一些指针。
呵呵，而在我的程序里，其实没有表示连接关系的数据结构。因为，不需要。这就是理论与实际的差别。
在我的程序中用到了图，用到了队列，但你不会看教科书中那一堆指针和矩阵。具体问题要具体分析，不能死板的套用。
在我的程序中，变量s表示一个状态结点，在我上述的结点表示方式下初始状态就是一个数值0x504321，即ABCDE*。由于我是从低位到高位表示这些格子的顺序的，所有看起来是倒过来的。最高位的5表示空格在第6个格子里（第一个格子用0表示）。
q数组充当一个队列的角色，列头是init中的循环变量i，列尾是len。通过这个队列来实现对图的广度优先搜索。
搜索的方式是从初始结点开始，搜索由这个结点通过可能的四个方向的移动所能到达的结点，如果这个结点已经包含在了连通子集里则跳过，如果不在连通子集里则把它加到子集里，同时也把它添加到搜索队列的尾部。重复从队列的头部取出结点进行上述的判断，直至队列中没有结点为止，之时我们就找出了所有与初始结点连通的结点。
而这些连通的结点则存储在数组F里。请注意，我的F数组只是一个字符型（我的用法实际是一个8位有符号整型）一维数组。
它存储的并不是一个完整的结点的细节，而是这个结点“是否属于连通集”这一关系。F[i] = 0表示结点i属于连通集，F[i] = 0表示结点i不属于连通集。
为什么存储的是一种关系而不是一个实际的结点呢？
存储实际的结点是完全可以的，但当我们需要查看某个结点是不是存在于这个集合中时就需要遍历这个集合。最简单的遍历其效率是O(n)，排序后使用二分法要O(logn)。
而且这种查寻操作贯穿于这个集合的结点添加过程中，二分查找随然缩短了查找的时间，但代价是增加了结点的添加时间（对于直接遍历，结点只需要添加到不尾即可；对于二分法需要数组有序，从而需要进行插入操作）。所以二分法的使用在这里没有实际意义。
而存储关系，则免去了这种查找的过程。要查看结点x是不是在连通集合里只需要查看一下F[x]的值。要将结点x添加到连通集合里也只需要将F[x]置1。这些操作的效率是O(1)。
需要注意的是，对于我的数组F，其下标的值并不是状态s的值。它们之间存在一种映射关系。
虽然直接使用s的值也是可以的（这样也很简洁），但请注意，s值的有效位数共28位，两亿多，约64M，这个内存消耗太大了（虽然对于你的电脑来说这不算什么，但ACM题目对于内存的使用量是有严格限制的，一般最大也就64M，其中还包含代码段所占用的内存）。
所以在我的代码中F的下标值用的是状态的6进制表示值。具体的说初始状态是123450，它对应的F下标是 1 + 2 * 6 + 3 * 6^2 + 4 * 6^3 + 5 * 6^4 + 0 * 6^5。
代码中的trans函数完成的就是状态s到F下标的映射。这么做只是我觉得简单方便，你也可以换一种你觉得简单方便的映射关系。
6的6次方等于46656，这是我选择F数组尺寸的原因。当然其中有些元素是违反题目定义的，它们永远不会用到，比如F[0]、F[1]...。实际有意义的值只有720个，而被赋值为1的只有360个。
可不可以减少这部分被浪费的空间？可以。比如将状态到下标的映射关系改成全排列与对应顺序的映射可以只使用720个元素。
但相对于构造这一映射关系来说，我个人更愿意多浪费4万多个元素而使用现在这个更简单的映射关系。
由于时间关系，就讲到这儿吧，恕在下文采有限，没讲明白的地方可以追加提问，有好的意见欢迎批评指正。
最后简单介绍一下我代码中各函数的功能。
int move(int s, int i) 移动状态s表示的格子中第i个格子到空位（前提：保证第i个格子是可移动的）
int trans(int s) 获得状态s对应的F下标
void init() 完成包含初始状态结点的连通图的搜索，建立F数组。
程序代码：
#include<stdio.h>
char F[46656];
int move(int s, int i)
{
int d, j;
d = (s >> i * 4) & 0xf;
j = s >> 24;
s ^= d << i * 4;
s ^= d << j * 4;
s ^= (i ^ j) << 24;
return s;
}
int trans(int s)
{
int i, j;
for(i = j = 0; j < 6; j++, s >>= 4)
i = i * 6 + (s & 0xf);
return i;
}
void init()
{
int q[512] = {0x5054321}, len = 1, i, j, t;
for(i = 0; i < len; i++)
{
t = trans(q[i]);
if(F[t]) continue;
F[t] = 1;
j = q[i] >> 24;
if(j < 3 && !F[trans(t = move(q[i], j + 3))]) q[len++] = t;
if(j >= 3 && !F[trans(t = move(q[i], j - 3))]) q[len++] = t;
if(j != 0 && j != 3 && !F[trans(t = move(q[i], j - 1))]) q[len++] = t;
if(j != 2 && j != 5 && !F[trans(t = move(q[i], j + 1))]) q[len++] = t;
}
}
int main()
{
char s[8];
int n, i, j;
init();
for(scanf("%d", &n); n--; printf("%d\n", F[i]))
{
scanf("%s", s);
for(i = j = 0; j < 6; j++)
i = i * 6 + (s[j] == '*' ? 0 : s[j] - 'A' + 1);
}
return 0;
}
2013-11-09 21:36
