ACM：圖的BFS，走迷宮

題目：

一個網格迷宮由n行m列的單元格組成，每個單元格要麼是空地（用1表示），要麼是障礙物（用0來表示）。你的任務是找一條從起點到終點的最短移動序列，其中UDLR分别表示往上、下、左、右移動到相鄰單元格。任何時候都不能在障礙格中，也不能走到迷宮之外。起點和終點保證是空地。

分析：圖的BFS。

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

const int MAXN = 500;
int maze[MAXN][MAXN], vis[MAXN][MAXN], dist[MAXN][MAXN], fa[MAXN][MAXN], last_dir[MAXN][MAXN];
int n, m, xs, ys, xt, yt;

int dx[] = {-1, 1, 0, 0};
int dy[] = {0, 0, -1, 1};
char name[] = "UDLR";

void print_path(int x, int y) {      //以遞歸的方式列印路徑
	int fx = fa[x][y] / m;
    int fy = fa[x][y] % m;
    if(fx != x || fy != y) {
		print_path(fx, fy);
		putchar(name[last_dir[x][y]]);
    }
}

int dir[MAXN*MAXN];
void print_path2(int x, int y) {      //以疊代的方式列印路徑
	int c = 0;
	for(;;) {
		int fx = fa[x][y] / m;
		int fy = fa[x][y] % m;
		if(fx == x && fy == y) break;
		dir[c++] = last_dir[x][y];
		x = fx;
 		y = fy;
	}
	while(c--) putchar(name[dir[c]]);
}

queue<int> q;
void bfs(int x, int y) {
	int u = x*m+y;
	dist[x][y] = 0;   //初始化自己到自己的距離就是0
	fa[x][y] = u;     //起點的父親節點就是自己，友善後面的列印操作
	vis[x][y] = 1;   
	q.push(u);
	while(!q.empty()) {
		u = q.front();
		q.pop();
		x = u/m;
		y = u%m;
		for(int d = 0; d < 4; ++d) {
			int nx = x + dx[d];
			int ny = y + dy[d];
			if(nx >= 0 && nx < n && ny >= 0 && ny < m && maze[nx][ny] && !vis[nx][ny]) {
				int v = nx * m + ny;
				q.push(v);
				vis[nx][ny] = 1;
				dist[nx][ny] = dist[x][y] + 1;    //走的步數+1
				fa[nx][ny] = v;                   //記錄父親結點
				last_dir[nx][ny] = d;             //記錄現在這個節點到父親節點走的方向
			}
		}
	}
}

int main() {
	cin >> n >> m >> xs >> ys >> xt >> yt;
	for(int i = 0; i < n; ++i) {
		for(int j = 0; j < m; ++j) {
			cin >> maze[i][j];
		}
	}
	memset(vis, 0, sizeof(vis));
	bfs(xs, ys);
	print_path(xt, yt);
	cout << endl;
	print_path2(xt, yt);
	cout << endl;
	return 0;
}