三角迷宫

发布时间: 2017年6月19日 00:22   最后更新: 2017年6月20日 04:08   时间限制: 1000ms   内存限制: 128M

这里有45个数字组成的一个三角阵,数字分别是1、2、3、...、9不等。要求你每次从顶点A处开始,一步步地通过它相邻的数字走到对边为止:但是一定要全部通过1,2,3,....,9这些数字,缺一不可,顺序不限,也不得重复,更不许走回头路。
                A 1
                  3 6
                9 7 8
              2 6 3 9
             3 1 5 8 5
           5 9 4 6 3 2
          8 3 2 9 4 9 1
         6 5 7 4 1 2 8 7
       7 1 4 8 7 4 5 6 2
对上述三角迷宫,我们可以找到一条路线,A 处:139654278。你能找出这一条路线来吗?

输入有若干组测试数据,其第一行是整数n,表示三角迷宫的个数。接着有n 组测试数据,每一组是一个三角迷宫的描述,共9 行,第i 行上有i 个1 到9 之间的数字符号,i=1,2,„,9,每行上的数字符号之间有一个空格。两个三角迷宫之间有一个空行。

对输入中描述的每组三角迷宫,确定从顶点A 出发,可否一步步地通过它相邻的数字走到对边为止,使路径上包含1,2,3„9 这全部9 个数字,顺序不限,不要重复,不许走回头路。先输出“Case#:”,其中“#”是三角迷宫的组号。如果从该顶点出发,可以确定这样的路线,则在下一行上输出“Possible”,否则输出“Impossible”。

复制
2
1
3 6
9 7 8
2 6 3 9
3 1 5 8 5
5 9 4 6 3 2
8 3 2 9 4 9 1
6 5 7 4 1 2 8 7
7 1 4 8 7 4 5 6 2

4
3 6
9 7 8
2 6 3 9
3 1 5 8 5
5 9 4 6 3 2
8 3 2 9 4 9 1
6 5 7 4 1 2 8 7
7 1 4 8 7 4 5 6 2
Case 1:
Possible
Case 2:
Impossible

1556

old_judge search

old_judge_None