迷宫bfs POJ3984

时间:2021-10-24 14:31:24

#include<stdio.h> int map[5][5]={0,1,0,0,0,       0,1,0,1,0,       0,0,0,0,0,       0,1,1,1,0,       0,0,0,1,0}; int mx[4]={1,-1,0,0}; int my[4]={0,0,1,-1}; int q; typedef struct node {  int x;  int y;  int step;  int pre; }node; node dui[100]; int tou=0; int wei=1; void bfs() {  int nx;  int ny;  dui[tou].x=0;  dui[tou].y=0;  dui[tou].step=1;  dui[tou].pre =-1;  map[0][0]=0;  while(tou<wei)  {   if(dui[tou].x ==4&&dui[tou].y==4)   {    q=tou;    printf("%d\n",dui[tou].step);    break;   }   for(int i=0;i<4;i++)   {    nx=dui[tou].x +mx[i];    ny=dui[tou].y +my[i];    if(nx>=0&&nx<5&&ny>=0&&ny<5&&map[nx][ny]==0)    {     dui[wei].x =nx;     dui[wei].y =ny;     dui[wei].step =dui[tou].step +1;     map[nx][ny]=dui[tou].step +1;     dui[wei].pre =tou;     wei++;    }   }   tou++;  }

} void prin(int i) {  if(i==-1)   return;  prin(dui[i].pre );  printf("(%d,%d)\n",dui[i].x ,dui[i].y ); } int main() { bfs();  prin(q);  return 0; }