华为机试题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
输入:
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;
}