洛谷 P1126 机器人搬重物

题目描述

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

输入输出格式

输入格式：

第一行为两个正整数 N,M(N,M≤50)N,M(N,M \le 50)N,M(N,M≤50) ，下面 NNN 行是储藏室的构造， 000 表示无障碍， 111 表示有障碍，数字之间用一个空格隔开。接着一行有 444 个整数和 111 个大写字母，分别为起始点和目标点左上角网格的行与列，起始时的面对方向（东 EEE ，南 SSS ，西 WWW ，北 NNN ），数与数，数与字母之间均用一个空格隔开。终点的面向方向是任意的。

输出格式：

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

明显是宽搜。
首先要把网格图转化为点图，
其次对于每一个状态要存储三个信息行号列号方向。
注意走两步的情况一定要注意不能越过障碍物。

 #include<algorithm>

 #include<iostream>

 #include<cstring>

 #include<climits>

 #include<cstdio>

 #include<queue>

 #include<map>

 using namespace std;

 int n,m,sx,sy,dx,dy,ans=INT_MAX,c[][][],u[]={,,,-},v[]={,,-,};

 bool b[][];

 char dr[];

 struct cll

 {

     int x,y,dir;

 }tmp1,tmp2;

 queue<cll>q;

 map<char,int>mp;

 int main()

 {

     mp['E']=,mp['S']=,mp['W']=,mp['N']=;

     memset(c,-,sizeof(c));

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

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

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

         {

             int t;

             scanf("%d",&t);

             if(t==)

                 b[i][j]=b[i-][j]=b[i][j-]=b[i-][j-]=;

         }

     scanf("%d%d%d%d%s",&sx,&sy,&dx,&dy,&dr);

     tmp1.x=sx,tmp1.y=sy,tmp1.dir=mp[dr[]];

     q.push(tmp1);

     c[sx][sy][tmp1.dir]=;

     while(!q.empty())

     {

         tmp1=q.front();

         q.pop();

         for(int i=;i<=;i++)//Ç°½ø

         {

             tmp2.x=tmp1.x+i*u[tmp1.dir],tmp2.y=tmp1.y+i*v[tmp1.dir],tmp2.dir=tmp1.dir;

             if(tmp2.x>&&tmp2.x<n&&tmp2.y>&&tmp2.y<m&&!b[tmp2.x][tmp2.y])

             {

                 if(c[tmp2.x][tmp2.y][tmp2.dir]==-)

                 {

                     q.push(tmp2);

                     c[tmp2.x][tmp2.y][tmp2.dir]=c[tmp1.x][tmp1.y][tmp1.dir]+;

                 }

             }

             else

                 break;

         }

         tmp2.x=tmp1.x,tmp2.y=tmp1.y;//×ªÏò

         tmp2.dir=(tmp1.dir+)%;

         if(c[tmp2.x][tmp2.y][tmp2.dir]==-)

         {

             q.push(tmp2);

             c[tmp2.x][tmp2.y][tmp2.dir]=c[tmp1.x][tmp1.y][tmp1.dir]+;

         }

         tmp2.dir=(tmp1.dir+)%;

         if(c[tmp2.x][tmp2.y][tmp2.dir]==-)

         {

             q.push(tmp2);

             c[tmp2.x][tmp2.y][tmp2.dir]=c[tmp1.x][tmp1.y][tmp1.dir]+;

         }

     }

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

         if(c[dx][dy][i]!=-)

             ans=min(ans,c[dx][dy][i]);

     if(ans==INT_MAX)

         printf("-1\n");

     else

         printf("%d\n",ans);

     return ;

 }

巴特西

洛谷 P1126 机器人搬重物

题目描述

输入输出格式

输入输出样例

最新文章

热门文章