Finding Nemo(搜索)

http://poj.org/problem?id=2049

题意：有一个迷宫，迷宫中有墙、门和空地。有M道墙，每一道墙用(x,y,d,t)表示，(x,y)表示墙的起始坐标，（d=1，t）表示向上t个单位都是墙；（d=0，t）表示向右t个单位都是墙。

有N扇门，用(x,y,d)表示，(x,y)表示门的起始坐标，d=1，表示向上一个单位都是门；d=0，表示向右一个单位都是门。给出Nemo的起始位置（f1,f2）,问起点到（0,0）的最少要穿过的门。

表示对搜索的题很晕。。看到题不知道该怎么存，看了别人的题解才懂点。。

 #include <stdio.h>

 #include <algorithm>

 #include <string.h>

 #include <queue>

 using namespace std;

 const int INF=<<;

 const int N=;

 int dir[][]= {{-,},{,},{,-},{,}};

 int xx[N][N],yy[N][N];

 int dis[N][N];

 int max_x,max_y;

 int boundary(int x,int y)//边界判断

 {

     if(x> && x<=max_x && y<=max_y && y>)

         return ;

     return ;

 }

 int change(int x,int y,int d)//方向转换

 {

     if(d==) return yy[x-][y];

     if(d==) return yy[x][y];

     if(d==) return xx[x][y-];

     return xx[x][y];

 }

 int bfs(int x,int y)

 {

     queue<int>q;

     while(!q.empty()) q.pop();

     for (int i = ; i <= max_y; i++)

     {

         for (int j = ; j <= max_x; j++)

             dis[i][j] = INF;

     }

     dis[][]=;

     q.push();

     q.push();

     while(!q.empty())

     {

         int x1=q.front();

         q.pop();

         int y1=q.front();

         q.pop();

         for (int i = ; i < ; i++)

         {

             int dx = x1+dir[i][];

             int dy = y1+dir[i][];

             int turn = change(x1,y1,i);

             if(boundary(dx,dy) && dis[dx][dy]>dis[x1][y1]+turn)

             {

                 dis[dx][dy]=dis[x1][y1]+turn;//更新最小步数

                 q.push(dx);

                 q.push(dy);

             }

         }

     }

     int ans = dis[x][y]==INF?-:dis[x][y];

     return ans;

 }

 int main()

 {

     int n,m;

     int x,y,d,l;

     while(~scanf("%d%d",&n,&m))

     {

         if(n==-&&m==-) break;

         max_x = max_y = -;

         memset(xx,,sizeof(xx));

         memset(yy,,sizeof(yy));

         for (int i = ; i < n; i++)

         {

             scanf("%d%d%d%d",&x,&y,&d,&l);

             if(d)

             {

                 for (int j = ; j < l; j++)

                     yy[x][y+j+]=INF;

                 max_y=max(y+l+,max_y);

                 max_x=max(x+,max_x);

             }

             else

             {

                 for (int j = ; j < l; j++)

                 {

                     xx[x+j+][y]=INF;

                     max_y=max(y+,max_y);

                     max_x=max(x+l+,max_x);

                 }

             }

         }

         for (int i = ; i < m; i++)

         {

             scanf("%d%d%d",&x,&y,&d);

             if(d) yy[x][y+]=;

             else  xx[x+][y]=;

         }

         double sx,sy;

         int sx1,sy1;

         scanf("%lf%lf",&sx,&sy);

         sx1 = (int)sx+;

         sy1 = (int)sy+;

         if(!(sx>= && sx<= && sy>= && sy<=))//Nemo可能在迷宫外

             printf("0\n");

         else

             printf("%d\n",bfs(sx1,sy1));

     }

     return ;

 }

巴特西

Finding Nemo(搜索)

最新文章

热门文章