首页 > 代码库 > 【bfs】 poj 3984 maze 队列存储

【bfs】 poj 3984 maze 队列存储

#include <iostream> #include <stdio.h> #include <cstring> #define Max 0x7f7f7f7f using namespace std; int map[6][6]; int visited[6][6]; int dir[4][2]={{1,0},{-1,0},{0,-1},{0,1}}; int ans[6][6]; int pre[30]; struct node {     int x;     int y; }; node path[30]; void output(int head) {     int tmp=pre[head];     if(tmp==0)     {         printf("(%d, %d)\n",path[tmp].x,path[tmp].y);     }     else     {         output(tmp);     }      printf("(%d, %d)\n",path[head].x,path[head].y); } void bfs() {     memset(visited,0,sizeof(visited));     memset(ans,Max,sizeof(ans));     int head=0;     int tail=1;     pre[head]=-1;     path[head].x=0;     path[head].y=0;     visited[path[head].x][path[head].y]=1;     while(head<tail)     {         int x=path[head].x;         int y=path[head].y;         if(x==4 && y==4)         {             output(head);             return ;         }         for(int i=0;i<4;i++)         {             int xx=x+dir[i][0];             int yy=y+dir[i][1];             if(visited[xx][yy]==0 && xx>=0 && xx<5 && yy>=0 && yy<5 && map[xx][yy]!=1)             {                 path[tail].x=xx;                 path[tail].y=yy;                 pre[tail]=head;                 tail++;                 visited[xx][yy]=1;             }         }         head++;     } } int main() {//     freopen("in.txt","r",stdin);     int i,j;     for(i=0;i<5;i++)     {         for(j=0;j<5;j++)         {             scanf("%d",&map[i][j]);         }     }     bfs();     return 0; }

 

【bfs】 poj 3984 maze 队列存储