J

J - 迷宫问题

Time Limit:1000MS Memory Limit:65536KB 64bit IO Format:%I64d & %I64u

Description

定义一个二维数组：

int maze[5][5] = {

 0, 1, 0, 0, 0,

 0, 1, 0, 1, 0,

 0, 0, 0, 0, 0,

 0, 1, 1, 1, 0,

 0, 0, 0, 1, 0,

};

它表示一个迷宫，其中的1表示墙壁，0表示可以走的路，只能横着走或竖着走，不能斜着走，要求编程序找出从左上角到右下角的最短路线。

Input

一个5 × 5的二维数组，表示一个迷宫。数据保证有唯一解。

Output

左上角到右下角的最短路径，格式如样例所示。

Sample Input

Sample Output

(0, 0) (1, 0) (2, 0) (2, 1) (2, 2) (2, 3) (2, 4) (3, 4) (4, 4)

//就是最最基础的bfs

 1 #include <iostream>
 2 #include <string.h>
 3 using namespace std;
 4 
 5 int map[5][5];
 6 int ans[5][5];
 7 int num=99999;
 8 
 9 void read_map()
10 {
11     memset(map,0,25*sizeof(int));
12     memset(ans,0,25*sizeof(int));
13     for (int i=0;i<5;i++)
14     {
15         for (int j=0;j<5;j++)
16         {
17             cin>>map[i][j];
18         }
19     }
20 }
21 
22 void copy_map()
23 {
24     for (int i=0;i<5;i++)
25     {
26         for (int j=0;j<5;j++)
27         {
28             ans[i][j]=map[i][j];
29         }
30     }
31 }
32 
33 void find_way(int x,int y,int all)
34 {
35     map[x][y]=2;
36     if (x==4&&y==4&&all<=num)
37     {
38         copy_map();//复制到ans里去;
39         num=all;
40         map[x][y]=0;
41     }
42     else
43     {
44         if (x+1<5&&map[x+1][y]==0) find_way(x+1,y,all+1);
45         if (y+1<5&&map[x][y+1]==0) find_way(x,y+1,all+1);
46         if (x-1>-1&&map[x-1][y]==0) find_way(x-1,y,all+1);
47         if (y-1>-1&&map[x][y-1]==0) find_way(x,y-1,all+1);
48         map[x][y]=0;
49     }
50 }
51 
52 void show_ans(int x,int y)
53 {
54     ans[x][y]=0;
55     if (x==4&&y==4)
56     {
57         cout<<"("<<x<<", "<<y<<")"<<endl;
58         return;
59     }
60     else
61     {
62         if (x+1<5&&ans[x+1][y]==2)
63         {
64             cout<<"("<<x<<", "<<y<<")"<<endl;
65             show_ans(x+1,y);
66         }
67         if (y+1<5&&ans[x][y+1]==2)
68         {
69             cout<<"("<<x<<", "<<y<<")"<<endl;
70             show_ans(x,y+1);
71         }
72         if (x-1>-1&&ans[x-1][y]==2)
73         {
74             cout<<"("<<x<<", "<<y<<")"<<endl;
75             show_ans(x-1,y);
76         }
77         if (y-1>-1&&ans[x][y-1]==2)
78         {
79             cout<<"("<<x<<", "<<y<<")"<<endl;
80             show_ans(x,y-1);
81         }
82     }
83 }
84 
85 int main()
86 {
87     read_map();
88     find_way(0,0,0);
89     show_ans(0,0);
90     return 0;
91 }

View Code