题目描述

深度优先搜索(Depth-First Search)，简称DFS
现在有一个m*n的正方形迷宫，使用DFS从迷宫的出发点(1,1)走到终点(m,n)。

输入

输入两个整数m n先行后列
以后n行，每行m个数字
并且规定1为墙 0为空

输出

如果可以到达终点，输出n行，每行m个数字，并且用*来表示所有的可行路径
否则输出ID Error

样例 #1

样例输入#1

5 4
01101
01101
00001
11100

样例输出#1

*1101
*1101
****1
111**

样例 #2

样例输出#2

3 3
000
000
000

样例输出#2

***
***
***

样例 #2

样例输出#2

2 2
01
10

样例输出#2

ID Error

数据范围与提示

$m≤100$
$n≤100$

提示

DFS

可以简单理解为一条路走到黑，标准的DFS一般要使用回溯递归

解题思路

对于下标越界处理

本题使用DFS解决，为了防止运行中的下标越界问题，对于输入的数进行简单处理 ：在迷宫外围加上一圈墙壁

01
00

变成

1111
1011
1001
1111

---

对于路径输出

可以使用bool数组来记录路径的使用情况，每次DFS运行成功的时候，把所有经过的路径进行标记，在输出的时候进行判断

代码实现

第一步 数据输入

cin>>m>>n;
// 变量x y 从1开始计数，方便在外围加上墙壁的处理
for(int x=1;x<=n;i++){//先行后列
  for(int y=1;y<=m;y++){
      char in;//一个个的输入
      cin>>in;
      map[x][y]=in-'0';
  }
}

使用for循环加上墙壁//不赘述

---

第二步 DFS

递归初始化

DFS(1,1);//从起点出发

递归使用

void dfs(int x,int y){
	if(x==m && y==n){//成功路径
    //标记路径
		for(int i=1;i<=n;i++){
			for(int j=1;j<=m;j++){
				if(use[i][j]==1)map[i][j]=-1;
        //路径标记为   -1
        //墙标记为	 	1
        //空气标记为 	0
			}
		}
		state=1;//判断是否为ID Error
		return;
	}
	use[x][y]=1;//标记节点
  //依次向四面盐生
  //判断该节点是否被使用 并且 不能为墙壁
	if(use[x+1][y]==0 && map[x+1][y]!=1)dfs(x+1,y);
	if(use[x][y+1]==0 && map[x][y+1]!=1)dfs(x,y+1);
	if(use[x-1][y]==0 && map[x-1][y]!=1)dfs(x-1,y);
	if(use[x][y-1]==0 && map[x][y-1]!=1)dfs(x,y-1);
	use[x][y]=0;//回溯
}

---

第三步输出

if(!state)//没有路径
那么输出ID Error

---

否则打印map//不过多赘述
这里提供一种方便的输出方式
map[x][y]>=0 ? map[x][y] : '*'
如果map为正数那么直接输出
否则输出*