称号：

网络格迷宫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;

}