题解 | #迷宫问题#
迷宫问题
https://www.nowcoder.com/practice/cf24906056f4488c9ddb132f317e03bc
使用广度优先搜索算法,确定最短路径,输出行走路径的时候可以从终点倒溯。
#include <iostream> #include <vector> #include <queue> using namespace std; int main() { int m, n; cin >> n >> m; vector<vector<int>> maze(n, vector<int>(m, 0)); vector<vector<int>> mark(n, vector<int>(m, 0)); vector<pair<int, int>> path; for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { cin >> maze[i][j]; } } queue<pair<int, int>> walk; walk.push({0, 0}); mark[0][0] = 1; while(!walk.empty()) { pair<int, int> temp = walk.front(); if (temp.first == n - 1 && temp.second + 1 == m - 1) { mark[temp.first][temp.second + 1] = 1; break; } else if (temp.first + 1 == n - 1 && temp.second == m - 1) { mark[temp.first + 1][temp.second] = 1; break; } walk.pop(); if (temp.first + 1 < n && mark[temp.first + 1][temp.second] != 1 && maze[temp.first + 1][temp.second] != 1) { walk.push({temp.first + 1, temp.second}); mark[temp.first + 1][temp.second] = 1; } if (temp.second + 1 < m && mark[temp.first][temp.second + 1] != 1 && maze[temp.first][temp.second + 1] != 1) { walk.push({temp.first, temp.second + 1}); mark[temp.first][temp.second + 1] = 1; } if (temp.first - 1 >= 0 && mark[temp.first - 1][temp.second] != 1 && maze[temp.first - 1][temp.second] != 1) { walk.push({temp.first - 1, temp.second}); mark[temp.first - 1][temp.second] = 1; } if (temp.second - 1 >= 0 && mark[temp.first][temp.second - 1] != 1 && maze[temp.first][temp.second - 1] != 1) { walk.push({temp.first, temp.second - 1}); mark[temp.first][temp.second - 1] = 1; } } int i, j, k, l; k = n - 1; l = m - 1; if (mark[k - 1][l] == 1) { i = k - 1; j = l; } else { i = k; j = l - 1; } path.push_back({k, l}); path.push_back({i, j}); while (!(i == 0 && j == 0)) { if (i - 1 >= 0 && mark[i - 1][j] == 1 && i - 1 != k) { k = i; l = j; i = i - 1; } else if (i + 1 < n && mark[i + 1][j] == 1 && i + 1 != k) { k = i; l = j; i = i + 1; } else if (j - 1 >= 0 && mark[i][j - 1] == 1 && j - 1 != l) { k = i; l = j; j = j - 1; } else if (j + 1 < m && mark[i][j + 1] == 1 && j + 1 != l) { k = i; l = j; j = j + 1; } path.push_back({i, j}); } for (int i = path.size() - 1; i >= 0; i--) { cout << '(' << path.at(i).first << ',' << path.at(i).second << ')' << endl; } return 0; } // 64 位输出请用 printf("%lld")
中等(算法题解) 文章被收录于专栏
中等难度题目