题目描述：
定义一个二维数组N*M（其中2<=N<=10;2<=M<=10），如5 × 5数组下所示：
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表示可以走的路，只能横着走或竖着走，不能斜着走，要求编程序找出从左上角到右下角的最短路线。入口点为[0,0],既第一空格是可以走的路。
Input
一个N × M的二维数组，表示一个迷宫。数据保证有唯一解,不考虑有多解的情况，即迷宫只有一条通道。
Output
左上角到右下角的最短路径，格式如样例所示。
Sample Input
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
Sample Output
(0, 0)
(1, 0)
(2, 0)
(2, 1)
(2, 2)
(2, 3)
(2, 4)
(3, 4)
(4, 4)
输入：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
输出：(0,0) (1,0) (2,0) (2,1) (2,2) (2,3) (2,4) (3,4) (4,4)
代码：
1 #include<iostream>View Code
2 #include<vector>
3 using namespace std;
4
5 struct point
6 {
7 int x;
8 int y;
9 };
10
11 static int a[100][100];
12 static int book[100][100];
13 int next[4][2]={{0,1},{1,0},{0,-1},{-1,0}};
14 int tx=0,ty=0;
15 int m,n;
16 int themax=9999;
17 vector<point> minway;
18 vector<point> way;
19 point xy;
20
21 int dfs(int x,int y,int step)
22 {
23 if(x==m-1&&y==n-1)
24 {
25 if(step<themax)
26 {
27 themax=step;
28 minway=way;
29 }
30 return 0;
31 }
32 int k=0;
33 for(k=0;k<4;k++)
34 {
35 tx=x+next[k][0];
36 ty=y+next[k][1];
37 if(tx<0||tx>=m||ty<0||ty>=n)
38 continue;
39 if(a[tx][ty]==0&&book[tx][ty]==0)
40 {
41 xy.x =tx;
42 xy.y =ty;
43 way.push_back (xy);
44 book[tx][ty]=1;
45 dfs(tx,ty,step+1);
46 book[tx][ty]=0;
47 way.pop_back ();
48 }
49 }
50 return 0;
51 }
52
53 int main()
54 {
55 cin>>m>>n;
56 int i,j;
57 for(i=0;i<m;i++)
58 {
59 for(j=0;j<n;j++)
60 {
61 cin>>a[i][j];
62 }
63 }
64 book[0][0]=1;
65 xy.x=0;
66 xy.y=0;
67 way.push_back (xy);
68 dfs(0,0,1);
69 // cout<<themax<<endl;
70 for(i=0;i<minway.size ();i++)
71 {
72 cout<<'('<<minway[i].x <<','<<minway[i].y <<')'<<endl;
73 }
74 }