题解 | #迷宫问题#

迷宫问题

https://www.nowcoder.com/practice/cf24906056f4488c9ddb132f317e03bc

#include <iostream>
#include <vector>
using namespace std;
//判断是否是单一方向通路。如果是，则返回相应方向d(down),r(right),u(up),l(left);如果不是，返回f(false)
char singledirection(pair<int, int>pos, vector<vector<int>> maze) {
    if (pos.first + 1 <= maze.size() - 1 &&
            maze[pos.first + 1][pos.second] == 0
            && !(pos.second + 1 <= maze[0].size() - 1 &&
                 maze[pos.first][pos.second + 1] == 0)
            && !(pos.first - 1 >= 0 &&
                 maze[pos.first - 1][pos.second] == 0)
            && !(pos.second - 1 >= 0 &&
                 maze[pos.first][pos.second - 1] == 0)) {
        return 'd';
    }
    if (pos.second + 1 <= maze[0].size() - 1 &&
            maze[pos.first][pos.second + 1] == 0
            && !(pos.first + 1 <= maze.size() - 1 &&
                 maze[pos.first + 1][pos.second] == 0)
            && !(pos.first - 1 >= 0 &&
                 maze[pos.first - 1][pos.second] == 0)
            && !(pos.second - 1 >= 0 &&
                 maze[pos.first][pos.second - 1] == 0)) {
        return 'r';
    }
    if (pos.first - 1 >= 0 &&
            maze[pos.first - 1][pos.second] == 0
            && !(pos.first + 1 <= maze.size() - 1 &&
                 maze[pos.first + 1][pos.second] == 0)
            && !(pos.second + 1 <= maze[0].size() - 1 &&
                 maze[pos.first][pos.second + 1] == 0)
            && !(pos.second - 1 >= 0 &&
                 maze[pos.first][pos.second - 1] == 0)) {
        return 'u';
    }
    if (pos.second - 1 >= 0 &&
            maze[pos.first][pos.second - 1] == 0
            && !(pos.first + 1 <= maze.size() - 1 &&
                 maze[pos.first + 1][pos.second] == 0)
            && !(pos.second + 1 <= maze[0].size() - 1 &&
                 maze[pos.first][pos.second + 1] == 0)
            && !(pos.first - 1 >= 0 &&
                 maze[pos.first - 1][pos.second] == 0)) {
        return 'l';
    }
    return 'f';
}
void solution(pair<int, int>pos, vector<vector<int>> maze,
              vector<pair<int, int>> route, vector<vector<pair<int, int>>>& routes) {
  //如果是单一方向且当前位置pos(position)不是终点，1.将当前位置记录至路径route 2.当前位置地图maze值设为1（不可通过）3.pos向相应方向移动
    while (singledirection(pos, maze) != 'f' && !(pos.first == maze.size() - 1 &&
            pos.second == maze[0].size() - 1)) {
        char direction = singledirection(pos, maze);
        if (direction == 'd') {
            route.push_back(pos);
            maze[pos.first][pos.second] = 1;
            pos.first++;
        } else if (direction == 'r') {
            route.push_back(pos);
            maze[pos.first][pos.second] = 1;
            pos.second++;
        } else if (direction == 'u') {
            route.push_back(pos);
            maze[pos.first][pos.second] = 1;
            pos.first--;
        } else if (direction == 'l') {
            route.push_back(pos);
            maze[pos.first][pos.second] = 1;
            pos.second--;
        }
    }
  //当前位置pos为终点，将pos记录进route，并将route记录进routes
    if (pos.first == maze.size() - 1 && pos.second == maze[0].size() - 1) {
        route.push_back(pos);
        routes.push_back(route);
    }
  //当前位置pos有多个方向通路，按下、右，上，左顺序处理
    if (pos.first + 1 <= maze.size() - 1 &&
            maze[pos.first + 1][pos.second] == 0) {
        vector<pair<int, int>> route_copy(route);
        vector<vector<int>> maze_copy(maze);
        pair<int, int>pos_copy = pos;
        route_copy.push_back(pos);
        maze_copy[pos.first][pos.second] = 1;
        pos_copy.first++;
        solution(pos_copy, maze_copy, route_copy, routes);
        maze[pos.first + 1][pos.second] = 1;
        solution(pos, maze, route, routes);
    }
    if (pos.second + 1 <= maze[0].size() - 1 &&
            maze[pos.first][pos.second + 1] == 0) {
        vector<pair<int, int>> route_copy(route);
        vector<vector<int>> maze_copy(maze);
        pair<int, int>pos_copy = pos;
        route_copy.push_back(pos);
        maze_copy[pos.first][pos.second] = 1;
        pos_copy.second++;
        solution(pos_copy, maze_copy, route_copy, routes);
        maze[pos.first][pos.second + 1] = 1;
        solution(pos, maze, route, routes);
    }
    if (pos.first - 1 >= 0 &&
            maze[pos.first - 1][pos.second] == 0) {
        vector<pair<int, int>> route_copy(route);
        vector<vector<int>> maze_copy(maze);
        pair<int, int>pos_copy = pos;
        route_copy.push_back(pos);
        maze_copy[pos.first][pos.second] = 1;
        pos_copy.first--;
        solution(pos_copy, maze_copy, route_copy, routes);
        maze[pos.first - 1][pos.second] = 1;
        solution(pos, maze, route, routes);
    }
    if (pos.second - 1 >= 0 &&
            maze[pos.first][pos.second - 1] == 0) {
        vector<pair<int, int>> route_copy(route);
        vector<vector<int>> maze_copy(maze);
        pair<int, int>pos_copy = pos;
        route_copy.push_back(pos);
        maze_copy[pos.first][pos.second] = 1;
        pos_copy.second--;
        solution(pos_copy, maze_copy, route_copy, routes);
        maze[pos.first][pos.second - 1] = 1;
        solution(pos, maze, route, routes);
    }
}
int main() {
    int m, n;
    while (cin >> m >> n) { // 注意 while 处理多个 case
        vector<vector<int>> maze(m, vector<int>(n));
        for (auto& i : maze) {
            for (auto& j : i) {
                cin >> j;
            }
        }
        pair<int, int> pos(0, 0);
        vector<vector<pair<int, int>>> routes;
        vector<pair<int, int>> route;
        solution(pos, maze, route, routes);
        int min = 0;
        for (int i = 1; i < routes.size(); i++) {
            if (routes[min].size() > routes[i].size()) {
                min = i;
            }
        }
        for (auto& i : routes[min]) {
            cout << '(' << i.first << ',' << i.second << ')' << endl;
        }
    }
}
// 64 位输出请用 printf("%lld")

此题可使用递归的方式解决。

设置变量:

pos当前位置，maze迷宫地图，route已走过的路径，routes到达终点的路径的集合

设置方法singledirection判断当前位置是否只有一个方向的通路。如果是，返回方向。

设置方法solution(pos,maze,route,routes)

pos可分为三种情况