题解 | 迷宫问题

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

struct Grid {
	int x;
	int y;
};

int n, m, ans;
int direction[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
int a[105][105];
int vis[105][105];

void dfs(Grid *p, vector<Grid> *path) {
	if (p -> x == n - 1 && p -> y == m - 1) {
		for (vector<Grid>::iterator it = path -> begin() ;it != path -> end(); it++) {
			cout << "(" << it -> x << "," << it -> y << ")" << endl; 
		}
		cout << "(" << p -> x << "," << p -> y << ")" << endl;
		return;
	}
	for (int k = 0; k < 4; k++) {
		int x = p -> x + direction[k][0];
		int y = p -> y + direction[k][1];
		if (x < n && x > -1 && y < m && y > -1 && !vis[x][y] && a[x][y] != 1) {
			Grid p2;
			p2.x = x;
			p2.y = y;
			vis[p -> x][p -> y] = 1;
			path -> push_back(*p);
			dfs(&p2, path);
			path -> pop_back();
			vis[p -> x][p -> y] = 0;
		}
	}
}

//记录一下c++的vector一些语法
//vector.pop_back()是去除尾部的一个元素
//vector常见还支持insert(it ,val), erase(it), clear()且均为o(n)
int main() {
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cin >> a[i][j];
		}
	}
	Grid st;
	st.x = 0;
	st.y = 0;
	vector<Grid> v;
	dfs(&st, &v);
}