信息学奥赛一本通T1255-迷宫问题-题解（C++代码）DFS求最短路

解题思路:

注意事项:

参考代码:

#include <iostream>
#include <vector>
using namespace std;

int a[10][10]; // 迷宫+标记数组 
int nxt[4][2] = {1, 0, -1, 0, 0, 1, 0, -1}; // 辅助数组 
int minstep = 0x3f3f3f3f;
vector<pair<int, int> > v, ans;

void show() {
	for (int i = 0; i < ans.size(); ++i) 
		cout << "(" << ans[i].first << ", " << ans[i].second << ")" << endl; 
}

void dfs(int x, int y, int step) {
	if (step >= minstep) return;
	if (x < 0 || x > 4 || y < 0 || y > 4) return;
	if (a[x][y]) return;
	if (x == 4 && y == 4) {
		ans = v, minstep = step;
		return;
	}
	v.push_back(make_pair(x, y));
	a[x][y] = -1;
	for (int i = 0; i < 4; ++i) 
		dfs(x + nxt[i][0], y + nxt[i][1], step + 1);
	v.pop_back();
	a[x][y] = 0;
}
 
int main() {
	for (int i = 0; i < 5; ++i)
		for (int j = 0; j < 5; cin >> a[i][j++]);
	dfs(0, 0, 0);
	show();
	cout << "(4, 4)" << endl;
	return 0;
}