描述
定义一个二维数组 N*M ，如 5 × 5 数组下所示：
int maze[5][5] = {
0, 1, 0, 0, 0,
0, 1, 1, 1, 0,
0, 0, 0, 0, 0,
0, 1, 1, 1, 0,
0, 0, 0, 1, 0,
};
它表示一个迷宫，其中的1表示墙壁，0表示可以走的路，只能横着走或竖着走，不能斜着走，要求编程序找出从左上角到右下角的路线。入口点为[0,0],既第一格是可以走的路。
数据范围： 2≤n,m≤10 ， 输入的内容只包含 0≤val≤1
输入描述：
输入两个整数，分别表示二维数组的行数，列数。再输入相应的数组，其中的1表示墙壁，0表示可以走的路。数据保证有唯一解,不考虑有多解的情况，即迷宫只有一条通道。
输出描述：
左上角到右下角的最短路径，格式如样例所示。
示例1
输入：
5 5
0 1 0 0 0
0 1 1 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)
示例2
输入：
5 5
0 1 0 0 0
0 1 0 1 0
0 0 0 0 1
0 1 1 1 0
0 0 0 0 0
输出：
(0,0)
(1,0)
(2,0)
(3,0)
(4,0)
(4,1)
(4,2)
(4,3)
(4,4)
说明：
注意：不能斜着走！！
解题思路：
这道题我们使用深度优先搜索（DFS）来解题。
假设我们在迷宫内的某一点（i，j），且该点周围不存在障碍，也不靠墙，我们下一步可以去到的位置是：向右，（i，j+1）；向下，（i+1，j）；向左，（i，j-1）；向上，（i-1，j）。
可以想象一下，假设我们在迷宫内的某一点，我们采取的方法就是试探，由于只能横着走或竖着走，所以我们只能往上下左右走，这里我们给这4个方向定一个优先级，比如所在之处，可以往多个方向走，我们先往哪个方向走？定的方向优先级为：右，下，左，上。就是说，如果先试探的方向右是障碍或者墙壁，那肯定不能走，那么往下试探，发现往下遇到障碍，那也不能走，直到遇到一个方向可以通行；因为题目要求最短路径，那么走过的位置就不能再走了，不然可以在某个位置反复横跳，最后再去终点，这也算一种路径，显然这也没有意义。
举个例子：
0 1 0 0 0
0 1 0 1 0
0 0 0 0 1
0 1 1 1 0
0 0 0 0 0
按照我们上述提到右下左上原则，迷宫里的人会按照红色字体先走：
0 1 0 0 0
1 1 0 1 0
2 3 4 5 1
0 1 1 1 0
0 0 0 0 0
这时候会发现走到死胡同里了，5的右边下边上边都是障碍，左边是已经走过的路，这个时候该怎么走？
我们在迷宫里迷路了也只能往回走，再试试其他的路能否走通到达目的地，这叫回溯。
于是我们往回撤一步，并将5这个位置标记为没走过，从4这个位置再重新开始试探，由于往右到5已经试过了，不能走通，往下是障碍，左边3已经走过了，那就只能往上走，肉眼可见那是一条死胡同，到最后肯定会回到4这个位置，这时候右下左上都试探过了，没有能走通，那就再往会撤一步，并将4这个位置标记为没走过，从3这个位置再重新开始试探，发现3没有方向可以走通，回溯到2，从2开始，继续试探，就会有以下路径：
0 1 0 0 0
1 1 0 1 0
2 0 0 0 1
3 1 1 1 0
4 5 6 7 8
按照这个思路，我们可以写代码了，我们用两个数组表示横向和纵向上的增量；
x_incre[4]={0,1,0,-1}, （横向）
y_incre[4]={1,0,-1,0}; （纵向）
第0次试探的方向是（i+0，y+1），即往右
第1次试探的方向是（i+1，y），即往下
……
用一个for循环来遍历试探每一个方向，可以减少重复代码。
用一个二维数组sign来标记某一点是否已经走过，初始化为0，走过后置为1，避免反复横跳。
由于要输出最短路径的各个坐标，我们可以用一个n行2列的二维数组记录每到一个点的坐标
下面为代码实现：
#include <stdio.h>
#define N 10
int sign[N][N],pos[1000][2],n,m,cnt,maze[N][N],flag;
void dfs(int x,int y)
{
pos[cnt][0]=x;pos[cnt][1]=y;cnt++; //pos二维数组记录到达位置的下标
sign[x][y]=1; //sign二维数组在相同位置值1，表示这个位置已经走过
if(x==n-1&&y==m-1)
{
flag=1;
return; //到达终点，flag置1，并返回上一级dfs递归调用
}
int i,j,k;
int x_incre[4]={0,1,0,-1},y_incre[4]={1,0,-1,0};
for(k=0;k<4;k++)
{
i=x+x_incre[k];j=y+y_incre[k]; //i，j为下次试探的位置
if(i>=0&&j>=0&&i<n&&j<m&&!maze[i][j]&&!sign[i][j])
{ //不能超出迷宫，也不能走障碍和已经走过的点
dfs(i,j); //进入下一步位置的试探
if(flag)
return; //试探的路径可以达到终点，返回上一级dfs调用
}
}
sign[i][j]=0; //如果没有试探出终点而返回，也没能在4次方向试探中找到可走的路
cnt--; //那么说明这个点走错了，标记这个点没走过，并将坐标弹出，结束这层dfs，返回上一层
}
int main()
{
int i,j,startx=0,starty=0;
scanf("%d%d",&n,&m);
for(i=0;i<n;i++)
for(j=0;j<m;j++)
scanf("%d",&maze[i][j]);
dfs(startx,starty); //起始位置为（0，0）
for(i=0;i<cnt;i++)
printf("(%d,%d)\n",pos[i][0],pos[i][1]);
return 0;
}
