SDNU 1086.迷宫问题（bfs标记路径）

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

int f[8][8], ii = 0;

struct node
{
    int x, y;
};

struct edge//记录每个点
{
    int x, y;
}e[8][8];

int path[4][2] = {0,1, 0,-1, 1,0, -1,0};

void bfs()
{
    queue<node>q;
    node p;
    p.x = 0;
    p.y = 0;
    q.push(p);
    while(!q.empty())
    {
        node l = q.front();
        q.pop();
        if(l.x == 4 && l.y == 4)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<5 && w.y<5 && !f[w.x][w.y])
            {
                f[w.x][w.y] = 1;
                e[w.x][w.y].x = l.x;//记录该点的上一个点，因为上一个点是确认的
                e[w.x][w.y].y = l.y;//记录该点的上一个点，因为上一个点是确认的
                q.push(w);
            }
        }
    }
}

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

int main()
{
    for(int i = 0; i<5; i++)
        for(int j = 0; j<5; j++)
            scanf("%d", &f[i][j]);
    f[0][0] = 1;
    bfs();
    print(4, 4);
    return 0;
}