华为机试题43-迷宫问题

描述

定义一个二维数组 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

输入：

输出：

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

示例2

输入：

输出：

(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;
}