poj3984(BFS且记录路径)

kuangbin带你飞专题:poj3984
这是一道bfs入门题，唯一不同的是需要对bfs的路径进行记录，所以用stl中的队列无法保存历史值，故采用数组模拟队列front和rear为头尾指针，再用递归模拟栈打印。
ac代码

#include <iostream>
#include <string.h>
#include <cstdio>
using namespace std;

typedef struct node{
    int x, y, pre;
    node(){}
    node(int x, int y, int pre)
    {
        this->x=x;
        this->y=y;
        this->pre=pre;
    }
};
int a[5][5];
int vis[5][5];
int dx[4]={0, 0, -1, 1};
int dy[4]={-1, 1, 0, 0};
const int maxn=10000;
node que[maxn];
void P(int pre)
{
    if(pre!=-1)
    P(que[pre].pre);
    else return;
    printf("(%d, %d)\n", que[pre].x, que[pre].y);
}
void bfs()
{
    int Front=0, Rear=1;
    node no=node(0, 0, -1);
    que[0]=no;
    vis[0][0]=1;
    while(Rear>Front)
    {
      //  printf("1 ");
        node N=que[Front];
        Front++;
        int x=N.x, y=N.y, nx, ny;
        for(int i=0; i<4; i++)
        {
            nx=x+dx[i], ny=y+dy[i];
            if(nx==4&&ny==4)
            {
                P(Front-1);
                printf("(4, 4)\n");
                return;
            }
            if(nx>=0&&nx<5&&ny>=0&&ny<5&&!vis[nx][ny]&&a[nx][ny]==0)
            {
                vis[nx][ny]=1;
                que[Rear++]=node(nx, ny, Front-1);
            }
        }
    }
}
int main(void)
{
    memset(vis, 0, sizeof(vis));
    for(int i=0; i<5; i++)
    {
        for(int j=0; j<5; j++)
        scanf("%d", &a[i][j]);
    }
    bfs();
    return 0;
}