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

解题思路:
这里就只说一下记录路径的问题吧，既然写到这个题目了，BFS和DFS基本用法都基本掌握了吧。

这里使用一位数组记录路径pre[i]:表示第i个坐标的紧相邻的上一个坐标，倒着来一直到0即可。

那么怎么把坐标存到一维数组里面呢（可以使用二位数组哈），比如坐标（i，j），那么讲5 * i + j存储到数组中就可表示坐标了，到时候取出的时候（x）只要x/5，x%5分别就是横纵坐标呢~
注意事项:

参考代码:

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

int a[10][10]; // 迷宫+标记数组 
int pre[30]; // 记录路径 
int nxt[4][2] = {1, 0, -1, 0, 0, 1, 0, -1}; // 辅助数组 

void show(int n) {
	if (!pre[n]) {
		cout << "(0, 0)" << endl;
		return;
	}
	show(pre[n]);
	cout << "(" << pre[n] / 5 << ", " << pre[n] % 5 << ")" << endl;
}

void bfs() {
	queue<pair<int, int> > q;
	q.push(make_pair(0, 0));
	a[0][0] = -1;
	while (!q.empty()) {
		int now_x = q.front().first, now_y = q.front().second;
		for (int i = 0; i < 4; ++i) {
			int new_x = now_x + nxt[i][0], new_y = now_y + nxt[i][1];
			if (new_x < 0 || new_x > 4 || new_y < 0 || new_y > 4) continue;
			if (a[new_x][new_y]) continue;
			pre[5 * new_x + new_y] = 5 * now_x + now_y;
			if (new_x == 4 && new_y == 4) {
				show(24); 
				return;
			}
			q.push(make_pair(new_x, new_y));
			a[new_x][new_y] = -1;
		}
		q.pop();
	}
}
 
int main() {
	for (int i = 0; i < 5; ++i)
		for (int j = 0; j < 5; cin >> a[i][j++]);
	bfs();
	cout << "(4, 4)" << endl;
	return 0;
}