SDNU 1220.Look for homework（BFS路径标记）

#include <cstdio>
#include <iostream>
#include <cmath>
#include <string>
#include <cstring>
#include <algorithm>
#include <queue>
#include <vector>
#include <map>
using namespace std;
#define ll long long

int n, m, position[18][18];
int path[4][2] = {1,0, 0,-1, 0,1, -1,0};
struct node
{
    int x, y;
};

struct edge
{
    int x, y, s = 0;
    char step;
} e[100+8][100+8];

void bfs()
{
    queue<node>q;
    node p;
    p.x = 0;
    p.y = 0;
    position[0][0] = 1;
    q.push(p);
    while(!q.empty())
    {
        node l = q.front();
        q.pop();
        if(l.x == n-1 && l.y == m-1)return;
        for(int i = 0; i<4; i++)
        {
            node w;
            w.x = l.x+path[i][0];
            w.y = l.y+path[i][1];
            if(w.x>=0 && w.y>=0 && w.x < n && w.y < m && !position[w.x][w.y])
            {
                position[w.x][w.y] = 1;
                e[w.x][w.y].s = e[l.x][l.y].s+1;
                e[w.x][w.y].x = l.x;//记录该点的上一个点，因为上一个点是确认的
                e[w.x][w.y].y = l.y;//记录该点的上一个点，因为上一个点是确认的
                if(i == 0)e[w.x][w.y].step = ‘D‘;
                else if(i == 1)e[w.x][w.y].step = ‘L‘;
                else if(i == 2)e[w.x][w.y].step = ‘R‘;
                else if(i == 3)e[w.x][w.y].step = ‘U‘;
                q.push(w);
            }
        }
    }
}

void print(int a, int b)
{
    if(a == 0 && b == 0)return;
    print(e[a][b].x, e[a][b].y);
    printf("%c", e[a][b].step);
}

int main()
{
    while(~scanf("%d%d", &n, &m))
    {
        char s[18][18];
        for(int i = 0; i < n; i++)scanf("%s", s[i]);
        for(int i = 0; i < n; i++)
            for(int j = 0; j < m; j++)
            {
                if(s[i][j] == ‘0‘)position[i][j] = 0;
                else position[i][j] = 1;
            }
        bfs();
        printf("%d\n", e[n-1][m-1].s);
        print(n-1, m-1);
        printf("\n");
    }
    return 0;
}