迷宫问题（只有一条路径）【dfs 判断是否继续dfs 的三种方法】

1. 迷宫问题（只有一条路径）

原题链接

dfs

迷宫问题总结：三种dfs判断

1. 迷宫dfs，最重要的一点是（也是dfs最重要的一点）就是需要先标记好走过的路径，因为标记好了以后，就不会再重复走.
   并且需要注意的是：如果dfs回溯的话，说明该节点走不通，不走这个节点，那么就需要把刚刚标记走过这个点，再重新改回不走这个点
2. dfs中如何判断是否继续dfs，有很多方法
   总结如下：

1. 先直接判断当前节点是否已经走过：这样的话，在接下来的步骤中，直接dfs就好，因为下一个dfs中会判断的
2. 定义一个判断函数，要往下走的dfs的话，先判断一下，如果可以走再dfs
3. dfs的返回值是 boolen类型的话，当遍历到结束点return true （那么就用if（合法）if（dfs）return true这样的一个递归也可以）方法三的代码如下

法三：

1. List<类> 存储过程节点

2. dfs的返回值是 boolen

dfs的结构是 if(合法)if(走到节点)return true；

import java.util.*;
// 题目已经提示了 【迷宫只有一条通道】，则直接使用 DFS 找路径就行了，如不有多条路径找最短考虑使用 BFS
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNextInt()) { // 注意 while 处理多个 case
            int n = in.nextInt();
            int m = in.nextInt();
            // 构造迷宫
            int[][] map = new int[n][m];
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < m; j++) {
                    map[i][j] = in.nextInt();
                }
            }
            
            // 路径存储的数组
            List<Pos> path = new ArrayList<>();
            // DFS 搜索路径
            dfs(map, 0, 0, path);
            // 输出
            for (Pos p : path) {
                System.out.println("(" + p.x + "," + p.y + ")");
            }
        }
    }
    
    // 返回值 标记是否找到可通行的路劲
    public static boolean dfs(int[][] map, int x, int y, List<Pos> path) {
        // 添加路径并标记已走
        path.add(new Pos(x, y));
        map[x][y] = 1;
        // 结束标志
        if (x == map.length - 1 && y == map[0].length - 1) {
            return true;
        }
        // 向下能走时
        if (x + 1 < map.length && map[x + 1][y] == 0) {
            if (dfs(map, x + 1, y, path)) {
                return true;
            }
        }
        // 向右能走时
        if (y + 1 < map[0].length && map[x][y + 1] == 0) {
            if (dfs(map, x, y + 1, path)) {
                return true;
            }
        }
        // 向上能走时
        if (x - 1 > -1 && map[x - 1][y] == 0) {
            if (dfs(map, x - 1, y, path)) {
                return true;
            }
        }
        // 向左能走时
        if (y - 1 > -1 && map[x][y - 1] == 0) {
            if (dfs(map, x, y - 1, path)) {
                return true;
            }
        }
        // 回溯
        path.remove(path.size() - 1);
        map[x][y] = 0;
        return false;
    }
    
    // 简单的位置类
    public static class Pos {
        int x;
        int y;
        
        public Pos(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79

法一：

1. 两个数组，一个存走过的路径，一个存地图

2. 如果合法再dfs

#include
using namespace std;
int mp[11][11],
    used[11][11]; //mp数组存储地图，used数组存储当前该位置是否已经走过
int n, m;
const int dx[4] = {1, -1, 0, 0}, dy[4] = {0, 0, 1, -1}; //dx和dy分别代表上下左右方向
int isValid(int posx, int posy) {
    if (posx >= 0 && posx < n && posy >= 0 && posy < m && !used[posx][posy] &&
            !mp[posx][posy]) return 1;
    return 0;
}//判断当前位置是否合法，（1）必须在迷宫范围内，（2）当前位置不能是墙壁，（3）当前位置不能走过
bool flag = true;
void dfs(int x, int y) {
    if (!flag) return; //已经输出了路径，不再搜索
    //printf("%d %d\n",x,y);
    if (x == n - 1 && y == m - 1) { //已到达终点就输出路径
        int i = 0, j = 0;
        do {
            cout << '(' << i << ',' << j << ')' << endl;
            used[i][j] = 0;
            if (used[i][j + 1]) j++;
            else if (used[i + 1][j])i++;
            else if (used[i - 1][j])i--;
            else if (used[i][j - 1])j--;
        } while (!(i == n - 1 && j == m - 1)); //只要没到终点就继续输出
        cout << '(' << n - 1 << ',' << m - 1 << ')' << endl; //输出终点
        flag = false;
    } else
        for (int i = 0; i <= 3; i++) {
            if (isValid(x + dx[i], y + dy[i])) { //若下一步是合法的
                used[x + dx[i]][y + dy[i]] = 1;    //搜索下一步的路径
                dfs(x + dx[i], y + dy[i]);
                used[x + dx[i]][y + dy[i]] = 0;
            }
        }
}
int main() {
    while (~scanf("%d%d", &n, &m)) { //输入地图规模
        flag = true;
        memset(used, 0, sizeof used);
        for (int i = 0; i < n; i++)
            for (int j = 0; j < m; j++)
                scanf("%d", &mp[i][j]); //读入地图
        used[0][0] = 1;
        dfs(0, 0);
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48

法二：

1. 在dfs函数最开始，如果节点不合法那么return

2. 那么在dfs过程中，四个方向直接dfs

#include
#include
using namespace std;

int n,m;
vector<vector<int>> maze;
//当从（0，0）到（n-1，m-1）有多条通路时，best_path记录最小的temp_path
//本题只有一条通路，所以当到达（n-1，m-1）时，让 best_path=temp_path即可
vector<vector<int>> best_path;
vector<vector<int>> temp_path;

void dfs(int i,int j)
{
    //边界条件：（1）数组越界（2）“墙壁”或已走过
    if(i<0||i>=n||j<0||j>=m||maze[i][j]==1)
    {
        return;
    }
    maze[i][j]=1;//该位置已走过标记为1
    temp_path.push_back({i,j});//将该位置加入路径
    if(i==n-1&&j==m-1)//走到终点
    {
        //多条路径时best_path记录最小的temp_path
        //if(temp_path.size()
        //{
        //    best_path=temp_path;
        //}
//本题只有一条通路，所以当到达（n-1，m-1）时，让 best_path=temp_path即可
        best_path=temp_path;
    }
    dfs(i-1,j);//上
    dfs(i+1,j);//下
    dfs(i,j-1);//左
    dfs(i,j+1);//右
    maze[i][j]=0;//该结点走不通时，恢复原场面
    temp_path.pop_back();//从路径中删除该节点
}

int main()
{
    while(cin>>n>>m)//一次测试中多个案例依次输入
    {
        maze=vector<vector<int>>(n,vector<int>(m,0));//设置地图的大小并初始化
        //一次测试中多个案例依次输入时，每个案例执行完后将路径容器清空
        best_path.clear();
        temp_path.clear();
        for(int i=0;i<n;i++)
        {
            for(int j=0;j<m;j++)
            {
                cin>>maze[i][j];
            }
        }
        dfs(0,0);
        for(vector<vector<int>>::iterator 
                               it=best_path.begin();it!=best_path.end();it++)
        {
            cout<<'('<<(*it)[0]<<','<<(*it)[1]<<')'<<endl;
        }
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62

2. 存储路径的方法

1. list + 类
2. 地图存储
3. map