【算法积累】计蒜客迷宫三问 (DFS & BFS)

心已赠人 2022-09-04 00:52 266阅读 0赞

# 计蒜客T1595 - 迷宫（一） #

[题目链接][Link 1]  
一天蒜头君掉进了一个迷宫里面，蒜头君想逃出去，可怜的蒜头君连迷宫是否有能逃出去的路都不知道。  
看在蒜头君这么可怜的份上，就请聪明的你告诉蒜头君是否有可以逃出去的路。  
**输入格式**  
第一行输入两个整数  n n n 和  m m m，表示这是一个  n × m n \\times m n×m 的迷宫。  
接下来的输入一个  n n n 行  m m m 列的迷宫。其中`S`表示蒜头君的位置，`*`表示墙，蒜头君无法通过，`.`表示路，蒜头君可以通过`.`移动，`T`表示迷宫的出口（蒜头君每次只能移动到四个与他相邻的位置——上，下，左，右）。  
**输出格式**  
输出一个字符串，如果蒜头君可以逃出迷宫输出`yes`，否则输出`no`。  
**数据范围**  
 1 ≤ n , m ≤ 10 1 \\le n, m \\le 10 1≤n,m≤10。  
**样例输入1**

3 4
    S**.
    ..*.
    ***T

**样例输出1**

**样例输入2**

3 4
    S**.
    ....
    ***T

**样例输出2**

yes

--------------------

解法：深度优先搜索 (DFS)  
语言：C++ (C++14)

#include <iostream>
    #include <vector>
    using namespace std;
    
    int n, m;
    char map[15][15];
    const int di[4][2] = { { 0, 1}, { 0, -1}, { 1, 0}, { -1, 0}};
    bool ans = false;
    
    void dfs(int x, int y) { 
        if (map[x][y] == 'T') { 
            ans = true;
            return;
        }
        map[x][y] = '#';
        for (auto & i : di) { 
            int x_next = x + i[0];
            int y_next = y + i[1];
            if (x_next >= 0 && x_next < n && y_next >= 0 && y_next < m && (map[x_next][y_next] == '.' || map[x_next][y_next] == 'T')) { 
                dfs(x_next, y_next);
            }
        }
    }
    
    int main() { 
        cin >> n >> m;
        for (int i = 0; i < n; i++) { 
            cin >> map[i];
        }
        for (int i = 0; i < n; i++) { 
            for (int j = 0; j < m; j++) { 
                if (map[i][j] == 'S') { 
                    dfs(i, j);
                }
            }
        }
        cout << (ans ? "yes" : "no") << endl;
        return 0;
    }

# 计蒜客T1596 - 迷宫（二） #

[题目链接][Link 2]  
蒜头君在你的帮助下终于逃出了迷宫，但是蒜头君并没有沉浸于喜悦之中，而是很快的又陷入了思考，从这个迷宫逃出的最少步数是多少呢？  
**输入格式**  
第一行输入两个整数  n n n 和  m m m，表示这是一个  n × m n \\times m n×m 的迷宫。  
接下来的输入一个  n n n 行  m m m 列的迷宫。其中 `S` 表示蒜头君的位置，`*`表示墙，蒜头君无法通过，`.`表示路，蒜头君可以通过`.`移动，`T`表示迷宫的出口（蒜头君每次只能移动到四个与他相邻的位置——上，下，左，右）。  
**输出格式**  
输出整数，表示蒜头君逃出迷宫的最少步数，如果蒜头君无法逃出迷宫输出  − 1 -1 −1。  
**数据范围**  
 1 ≤ n , m ≤ 10 1 \\le n, m \\le 10 1≤n,m≤10。  
**样例输入1**

3 4
    S**.
    ..*.
    ***T

**样例输出1**

-1

**样例输入2**

3 4
    S**.
    ....
    ***T

**样例输出2**

--------------------

解法：广度优先搜索 (BFS)  
语言：C++ (C++14)

#include <iostream>
    #include <queue>
    using namespace std;
    
    int n, m;
    char map[15][15];
    const int di[4][2] = { { 1, 0}, { 0, 1}, { -1, 0}, { 0, -1}};
    bool visited[15][15];
    struct node { 
        int x, y, cnt;
        node(int x1, int y1, int cnt1) { 
            x = x1;
            y = y1;
            cnt = cnt1;
        }
    };
    
    int bfs(int x, int y) { 
        queue<node> q;
        q.push(node(x, y, 0));
        visited[x][y] = true;
        while (!q.empty()) { 
            node cur = q.front();
            q.pop();
            for (auto & i : di) { 
                int x_next = cur.x + i[0];
                int y_next = cur.y + i[1];
                if (x_next >= 0 && x_next < n && y_next >= 0 && y_next < m && !visited[x_next][y_next] && map[x_next][y_next] != '*') { 
                    if (map[x_next][y_next] == 'T') { 
                        return cur.cnt + 1;
                    } else { 
                        visited[x_next][y_next] = true;
                        q.push(node(x_next, y_next, cur.cnt + 1));
                    }
                }
            }
        }
        return -1;
    }
    
    int main() { 
        cin >> n >> m;
        for (int i = 0; i < n; i++) { 
            cin >> map[i];
        }
        for (int i = 0; i < n; i++) { 
            for (int j = 0; j < m; j++) { 
                if (map[i][j] == 'S') { 
                    cout << bfs(i, j) << endl;
                }
            }
        }
        return 0;
    }

# 计蒜客T1597 - 迷宫（三） #

[题目链接][Link 3]  
经过思考蒜头君终于解决了怎么计算一个迷宫的最短路问题，于是蒜头君找到一个新的迷宫图，来验证自己是否真的会计算一个迷宫的最短路。  
为了检验自己计算的是否正确，蒜头君特邀你一起来计算。  
**输入格式**  
第一行输入两个整数  n n n 和  m m m，表示这是一个  n × m n \\times m n×m 的迷宫。  
接下来的输入一个  n n n 行  m m m 列的迷宫。其中`@`表示蒜头君的位置，`#`表示墙，蒜头君无法通过，`.`表示路，蒜头君可以通过`.`移动，所有在迷宫最外围的`.`都表示迷宫的出口（蒜头君每次只能移动到四个与他相邻的位置——上，下，左，右）。  
**输出格式**  
输出整数，表示蒜头君逃出迷宫的最少步数，如果蒜头君无法逃出迷宫输出  − 1 -1 −1。  
**数据范围**  
 1 ≤ n , m ≤ 15 1 \\le n,m \\le 15 1≤n,m≤15。  
**样例输入1**

9 13
    #############
    #@..........#
    #####.#.#.#.#
    #...........#
    #.#.#.#.#.#.#
    #.#.......#.#
    #.#.#.#.#.#.#
    #...........#
    #####.#######

**样例输出1**

**样例输入2**

4 6
    #.####
    #.#.##
    #...@#
    ######

**样例输出2**

--------------------

解法：广度优先搜索 (BFS)

> 这道题只是依据题意把迷宫（二）`bfs()`函数中的迷宫出口判断条件加以修改即可AC，即将return条件由判断`map[x_next][y_next] == 'T'`改为判断`map[x_next][y_next] == '.' && (x_next == 0 || x_next == n - 1 || y_next == 0 || y_next == m - 1)`。

语言：C++ (C++14)

#include <iostream>
    #include <queue>
    using namespace std;
    
    int n, m;
    char map[20][20];
    const int di[4][2] = { { 0, 1}, { 0, -1}, { -1, 0}, { 1, 0}};
    bool visited[20][20];
    struct node { 
        int x, y, cnt;
        node(int x1, int y1, int cnt1) { 
            x = x1;
            y = y1;
            cnt = cnt1;
        }
    };
    
    int bfs(int x, int y) { 
        queue<node> q;
        q.push(node(x, y, 0));
        visited[x][y] = true;
        while (!q.empty()) { 
            node cur = q.front();
            q.pop();
            for (auto & i : di) { 
                int x_next = cur.x + i[0];
                int y_next = cur.y + i[1];
                if (x_next >= 0 && y_next >= 0 && x_next < n && y_next < m && !visited[x_next][y_next] && map[x_next][y_next] != '#') { 
                    if (map[x_next][y_next] == '.' && (x_next == 0 || x_next == n - 1 || y_next == 0 || y_next == m - 1)) { 
                        return cur.cnt + 1;
                    } else { 
                        visited[x_next][y_next] = true;
                        q.push(node(x_next, y_next, cur.cnt + 1));
                    }
                }
            }
        }
        return -1;
    }
    
    int main() { 
        cin >> n >> m;
        for (int i = 0; i < n; i++) { 
            cin >> map[i];
        }
        for (int i = 0; i < n; i++) { 
            for (int j = 0; j < m; j++) { 
                if (map[i][j] == '@') { 
                    cout << bfs(i, j) << endl;
                }
            }
        }
        return 0;
    }

[Link 1]: https://nanti.jisuanke.com/t/T1595
[Link 2]: https://nanti.jisuanke.com/t/T1596
[Link 3]: https://nanti.jisuanke.com/t/T1597