maze（迷宫）

poj 3984

题目大意：

解决：bfs，关键是对路径的保存

#include <iostream>
#include <cstring>
#include <vector>
#include <queue>
using namespace std;
int map[5][5];

struct node
{
    int x,y;
};
//此处定义了一个存放上一个坐标的路径结构体，采用递归输出
node path[5][5];
queue<node> q;
int sx=1,sy=1;
int dx[]={1,-1,0,0};
int dy[]={0,0,1,-1};
int cnt=0;
node tmp;

void print(int x,int y)
{
    if(x!=-1 &&y!=-1)
    {
        print(path[x][y].x,path[x][y].y);
        printf("(%d, %d)\n",x,y);
    }
}
void bfs()
{
    tmp.x=0;
    tmp.y=0;
    path[0][0].x=-1;
    path[0][0].y=-1;
    q.push(tmp);
    while(!q.empty())
    {
        tmp=q.front();
        if(tmp.x==4 && tmp.y==4)break;
        q.pop();
        node tmp1;
        for(int i=0;i<4;i++)
        {
            tmp1.x=tmp.x+dx[i];
            tmp1.y=tmp.y+dy[i];
            if(!map[tmp1.x][tmp1.y] && tmp1.x>=0 && tmp1.x<5 && tmp1.y>=0 && tmp1.y<5 )
            {
                q.push(tmp1);
                    path[tmp1.x][tmp1.y].x=tmp.x;
                path[tmp1.x][tmp1.y].y=tmp.y;
               //此处也是易错点，由于访问过了，直接堵住回路就行了
                map[tmp.x][tmp.y]=1;
              }
        }
    }
  print(4,4);
   
}


int main()
{
    for(int i=0;i<5;i++)
      for(int j=0;j<5;j++)
       scanf("%d",&map[i][j]);
    bfs();
    system("pause");
    return 0;
}