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;
}
