称号：
网络格迷宫n行m单位列格组成，每个单元格无论空间（使用1表示），无论是障碍（使用0为了表示）。你的任务是找到一个动作序列最短的从开始到结束，其中UDLR同比分别增长、下一个、左、向右移动到下一个单元格。
不论什么时候都不能在障碍格中。也不能走到迷宫之外。
起点和终点保证是空地。
分析：图的BFS。
#include#include #include 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 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;}