P1126 机器人搬重物

题目描述

机器人移动学会（RMI）现在正尝试用机器人搬运物品。机器人的形状是一个直径1.6米的球。在试验阶段，机器人被用于在一个储藏室中搬运货物。储藏室是一个N*M的网格，有些格子为不可移动的障碍。机器人的中心总是在格点上，当然，机器人必须在最短的时间内把物品搬运到指定的地方。机器人接受的指令有：向前移动1步（Creep）；向前移动2步（Walk）；向前移动3步（Run）；向左转（Left）；向右转（Right）。每个指令所需要的时间为1秒。请你计算一下机器人完成任务所需的最少时间。

输入输出格式

输入格式：

输入的第一行为两个正整数N,M（N,M<=50），下面N行是储藏室的构造，0表示无障碍，1表示有障碍，数字之间用一个空格隔开。接着一行有四个整数和一个大写字母，分别为起始点和目标点左上角网格的行与列，起始时的面对方向（东E，南S，西W，北N），数与数，数与字母之间均用一个空格隔开。终点的面向方向是任意的。

输出格式：

一个整数，表示机器人完成任务所需的最少时间。如果无法到达，输出-1。

输入输出样例

输入样例#1：

9 10

0 0 0 0 0 0 1 0 0 0

0 0 0 0 0 0 0 0 1 0

0 0 0 1 0 0 0 0 0 0

0 0 1 0 0 0 0 0 0 0

0 0 0 0 0 0 1 0 0 0

0 0 0 0 0 1 0 0 0 0

0 0 0 1 1 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0

1 0 0 0 0 0 0 0 1 0

7 2 2 7 S

输出样例#1：

12

分析：机器人中心总在格点上，这也就是它走动时的中心是格点，而不是格子。我们可以将所有的格子化成点，一个格子化成四个点，
　　黑点优先。黑点优先是什么意思、？因为一个点化成四个点，那也就是需要 n*4,m*4个格子，但我们不用这么多，
　　其实n+1,m+1 个格子就可以了。怎么变呢，我们让黑点的化成四个黑点，其他的不变就可以了，题目中的样例处理完厚实这样(看下图，不大好看)

这样我们会发现，只要让机器人考虑机器人的中心就可以了，机器人中心不能到最外圈的格点，机器人的中心不能走黑点，其他的可以都不用考虑。
然后广搜就可以。
注意:要cin读入字符，（为什么不能 scanf("%d%d%d%d%c",&sx,&sy,&ex,&ey,&ch);读空格吗？样例都过了，还是60分。。)

 #include<cstdio>

 #include<algorithm>

 #include<queue>

 #include<iostream>

 using namespace std;

 const int N = ;

 struct node{

     int x,y,step;

     int to;

 }cur,nxt;

 queue<node>q;

 int a[N][N];

 int mp[N][N];

 int dx[]={,,,-};  //东南西北

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

 bool v[N][N][];

 int n,m,k,sx,sy,ex,ey;

 char ch;

 void init()

 {

     scanf("%d%d",&n,&m);

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

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

             scanf("%d",&a[i][j]);

     scanf("%d%d%d%d",&sx,&sy,&ex,&ey);

     cin>>ch;

     sx++; sy++; ex++; ey++;

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

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

             if(a[i][j]==)

             {

                 mp[i][j] = ;

                 mp[i+][j] = ;

                 mp[i][j+] = ;

                 mp[i+][j+] = ;

             }

     n++; m++;

 }

 void bfs()

 {

     if(sx==ex && sy==ey)

     {

         printf("0\n");

         return ;

     }

     cur.x = sx;

     cur.y = sy;

     cur.step = ;

     switch(ch)

     {

         case 'E': cur.to=;break;

         case 'S': cur.to=;break;

         case 'W': cur.to=;break;

         case 'N': cur.to=;break;

     }

     q.push(cur);

     v[sx][sy][cur.to] = true;

     while(!q.empty())

     {

         cur = q.front() ;

         q.pop();

         k = cur.to;

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

         {

             int xx = cur.x+i*dx[k];

             int yy = cur.y+i*dy[k];

             if(xx> && xx<n && yy> && yy<m && !mp[xx][yy])

             {

                 if(xx==ex && yy==ey)

                 {

                     printf("%d\n",cur.step+);

                     return;

                 }

                 if(v[xx][yy][k]) continue;

                 v[xx][yy][k]=true;

                 nxt.x = xx;

                 nxt.y = yy;

                 nxt.step = cur.step+;

                 nxt.to = k;

                 q.push(nxt);

             }

             else break;

         }

         nxt.x = cur.x;

         nxt.y = cur.y;

         nxt.step = cur.step+;

         nxt.to = (cur.to+)%;

         if(!v[nxt.x][nxt.y][nxt.to])

         {

             v[nxt.x][nxt.y][nxt.to] = true;

             q.push(nxt);

         }

         nxt.to = (cur.to-+)%;

         if(!v[nxt.x][nxt.y][nxt.to])

         {

             v[nxt.x][nxt.y][nxt.to] = true;

             q.push(nxt);

         }

     }

     printf("-1\n");

 }

 int main()

 {

     init();

     bfs();

     return ;

 }

巴特西

P1126 机器人搬重物

P1126 机器人搬重物

题目描述

输入输出格式

输入输出样例

最新文章

热门文章