题解 | #迷宫问题#
迷宫问题
https://www.nowcoder.com/practice/cf24906056f4488c9ddb132f317e03bc
#include <iostream> #include <vector> #include <queue> #include <utility> #include <stack> #include <string> using namespace std; int direction[4][2] = { {1,0},{-1,0},{0,1},{0,-1} //左,右,上,下 }; int main() { int n, m; cin >> n >> m; vector<vector<int> > arr(n, vector<int>(m)); vector<vector<int> > visited(n, vector<int>(m)); for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) cin >> arr[i][j]; //bfs queue<pair<int, int> > que; que.push(make_pair(0, 0)); while (!que.empty()) { pair<int, int> temp = que.front(); que.pop(); if (temp.first == n - 1 && temp.second == m - 1) { break; } for (int i = 0; i < 4; i++) { int x = temp.first + direction[i][0]; int y = temp.second + direction[i][1]; if (x >= 0 && y >= 0 && x < n && y < m && arr[x][y] == 0 && visited[x][y] == 0) { visited[x][y] = i + 1; que.push(make_pair(x, y)); } } } //入栈、出栈 stack<pair<int, int> > st; int x = n - 1; int y = m - 1; st.push(make_pair(x,y)); while (x > 0 || y > 0) { int xx = x - direction[visited[x][y] - 1][0]; int yy = y - direction[visited[x][y] - 1][1]; st.push(make_pair(xx, yy)); x = xx; y = yy; } while (!st.empty()) { pair<int, int> temp = st.top(); st.pop(); cout << "(" << temp.first << "," << temp.second << ")" << endl; } return 0; } // 64 位输出请用 printf("%lld")