题解 | #迷宫问题#

#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")