走迷宫

转载请注明出处

网址：http://www.codeup.cn/problem.php?id=2915

题目：走迷宫 maze [2*+]

题目描述

有一个m*n格的迷宫(表示有m行、n列)，其中有可走的也有不可走的，如果用1表示可以走，0表示不可以走，文件读入这m*n个数据和起始点、结束点 (起始点和结束点都是用两个数据来描述的，分别表示这个点的行号和列号)。现在要你编程找出所有可行的道路，要求所走的路中没有重复的点，走时只能是上下左右四个方向。如果一条路都不可行，则输出相应信息(用-l表示无路)。

Input

【输入】第一行是两个数m，n
(2<=m，n<=17)，
接下来是m行n列由1和0组成的数据，最后两行是起始点和结束点。

Output

【输出】所有可行的路径，描述一个点时用(x，y)的形式，除开始点外，其他的都要用“一>”表示方向。如果没有一条可行的路则输出-1。

Sample Input

【样例】	maze.in
			5 6
			1 0 0 1 0 1
			1 1 1 1 1 1 
			0 0 1 1 1 0
			1 1 1 1 1 0
			1 1 1 0 1 1
			1 1
			5 6

Sample Output

maze.out
(1,1)->(2,1)->(2,2)->(2,3)->(2,4)->(2,5)->(3,5)->(3,4)->(3,3)->(4,3)->(4,4)->(4,5)->(5,5)->(5,6)
(1,1)->(2,1)->(2,2)->(2,3)->(2,4)->(2,5)->(3,5)->(3,4)->(4,4)->(4,5)->(5,5)->(5,6)
(1,1)->(2,1)->(2,2)->(2,3)->(2,4)->(2,5)->(3,5)->(4,5)->(5,5)->(5,6)
(1,1)->(2,1)->(2,2)->(2,3)->(2,4)->(3,4)->(3,3)->(4,3)->(4,4)->(4,5)->(5,5)->(5,6)
(1,1)->(2,1)->(2,2)->(2,3)->(2,4)->(3,4)->(3,5)->(4,5)->(5,5)->(5,6)
(1,1)->(2,1)->(2,2)->(2,3)->(2,4)->(3,4)->(4,4)->(4,5)->(5,5)->(5,6)
(1,1)->(2,1)->(2,2)->(2,3)->(3,3)->(3,4)->(2,4)->(2,5)->(3,5)->(4,5)->(5,5)->(5,6)
(1,1)->(2,1)->(2,2)->(2,3)->(3,3)->(3,4)->(3,5)->(4,5)->(5,5)->(5,6)
(1,1)->(2,1)->(2,2)->(2,3)->(3,3)->(3,4)->(4,4)->(4,5)->(5,5)->(5,6)
(1,1)->(2,1)->(2,2)->(2,3)->(3,3)->(4,3)->(4,4)->(3,4)->(2,4)->(2,5)->(3,5)->(4,5)->(5,5)->(5,6)
(1,1)->(2,1)->(2,2)->(2,3)->(3,3)->(4,3)->(4,4)->(3,4)->(3,5)->(4,5)->(5,5)->(5,6)
(1,1)->(2,1)->(2,2)->(2,3)->(3,3)->(4,3)->(4,4)->(4,5)->(5,5)->(5,6)

Hint

【提高思考】：若本题要求输出最短的一条路则应使用宽搜

没有看出来它是按顺时针走，还是逆时针，不清楚他第一次递归往哪儿走。欢迎大神指导，评论。刚开始研究这块，欢迎讨论。

下面上代码：

 1 /**
 2 测试用例,方便复制测试
 3 5 6
 4 1 0 0 1 0 1
 5 1 1 1 1 1 1
 6 0 0 1 1 1 0
 7 1 1 1 1 1 0
 8 1 1 1 0 1 1
 9 1 1
10 5 6
11 */
12 #include <stdio.h>
13 
14 int m,n;///m行 n列
15 int table[20][20];
16 int stack0[400],top0 = 0;
17 int begin_x,begin_y;
18 int end_x,end_y;
19 
20 int top;
21 struct S{
22     int x,y;
23 }stack[400];
24 
25 void printStack(){
26     for(int i = 0; i < top - 1; i++){
27         printf("(%d,%d)->",stack[i].x,stack[i].y);
28     }
29     printf("(%d,%d)
",end_x,end_y);
30 }
31 
32 void recall(int coord_x,int coord_y){
33     int i;
34     if(table[coord_x][coord_y] == 0){///不可到达
35         stack0[top0++] = 0;
36         return ;
37     }else{///当前坐标从未到过 (table[coord_x][coord_y] == 1)
38         table[coord_x][coord_y] = 0;
39         stack0[top0++] = 1;
40         stack[top].x = coord_x;
41         stack[top].y = coord_y;
42         top++;
43     }
44 
45     if(coord_x == end_x && coord_y == end_y){
46         printStack();
47         return ;
48     }
49 
50     recall(coord_x, coord_y - 1);///左 且 可以走
51     if(stack0[--top0]){
52         table[coord_x][coord_y - 1] = 1;
53         top--;
54     }
55 
56     recall(coord_x, coord_y + 1);///右 且 可以走
57     if(stack0[--top0]){
58         table[coord_x][coord_y + 1] = 1;
59         top--;
60     }
61 
62     recall(coord_x - 1, coord_y);///上 且 可以走
63     if(stack0[--top0]){
64         table[coord_x - 1][coord_y] = 1;
65         top--;
66     }
67 
68     recall(coord_x + 1, coord_y);///下 且 可以走
69     if(stack0[--top0]){
70         table[coord_x + 1][coord_y] = 1;
71         top--;
72     }
73 
74 }
75 
76 int main(void){
77 
78     while(scanf("%d%d",&m,&n) != EOF){
79         top = top0 = 0;
80         for(int i = 0; i < 20; i++)
81             for(int j = 0; j < 20; j++){
82                 if(i == 0 || j == 0){///table边界不可走
83                     table[i][j] = 0;
84                     continue;
85                 }
86                 if(i < m + 1 && j < n + 1)
87                     scanf("%d",&table[i][j]);
88                 else
89                     table[i][j] = 0;
90             }
91         scanf("%d%d%d%d",&begin_x,&begin_y,&end_x,&end_y);
92         recall(begin_x, begin_y);
93     }
94     return 0;
95 }