机器人搬重物（BFS）-白红宇

机器人搬重物（BFS）

阅读量：7118 次

发布时间：2019-06-28

本文共 2440 字，大约阅读时间需要 8 分钟。

机器人搬重物

时间限制: 1 Sec 内存限制: 128 MB

提交: 22 解决: 10

[][][]

题目描述

机器人移动学会（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。

样例输入

9 100 0 0 0 0 0 1 0 0 00 0 0 0 0 0 0 0 1 00 0 0 1 0 0 0 0 0 00 0 1 0 0 0 0 0 0 00 0 0 0 0 0 1 0 0 00 0 0 0 0 1 0 0 0 00 0 0 1 1 0 0 0 0 00 0 0 0 0 0 0 0 0 01 0 0 0 0 0 0 0 1 07 2 2 7 S

样例输出

12 【分析】这个题目首先要注意几点。输入给的图是方格的，而机器人走的是方格的四个点，所以如果这个方格是障碍，那么这个方格的四个格点都不能走。  还有就是机器人的身子不能超过布局，所以边缘不能走。然后就是BFS咯，用一个结构体存当前格点的状态dir表示方向。

#include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               #include 
                
                 #include 
                 
                  #include 
                  
                   #include 
                   
                    #include
                    
                     #define mod 1000000007#define inf 0x3f3f3f3f#define pi acos(-1.0)using namespace std;typedef long long ll;const int N=55;const int M=1005;ll power(ll a,int b,ll c) {ll ans=1;while(b) { if(b%2==1) {ans=(ans*a)%c;b--;}b/=2;a=a*a%c;}return ans;}int d[4][2]={ 0,1,1,0,0,-1,-1,0};int mp[N][N],w[N][N];int vis[N][N][4];int n,m,sx,sy,ex,ey;char ch;bool flag=false;struct man{ int x,y,step; int dir;};bool check(man t,int I){ int xx,yy; for(int i=1;i<=I;i++){ xx=t.x+i*d[t.dir][0]; yy=t.y+i*d[t.dir][1]; if(xx<1||xx>=n||yy<1||yy>=m)return false; if(w[xx][yy]==1)return false; } if(vis[xx][yy][t.dir])return false; return true;}queue
                     
                      q;void bfs(){ while(!q.empty()){ man t=q.front();//printf("%d %d %d %d\n",t.x,t.y,t.dir,t.step); q.pop();//system("pause"); if(t.x==ex&&t.y==ey){ flag=true;cout<
                      
                       <
                       
                        3)dir=0; k.dir=dir;k.step++; if(vis[t.x][t.y][k.dir]==0)q.push(k),vis[t.x][t.y][k.dir]=1; man kk=t; dir=t.dir-1; if(dir<0)dir=3; kk.dir=dir;kk.step++; if(vis[t.x][t.y][kk.dir]==0)q.push(kk),vis[t.x][t.y][kk.dir]=1; }}int main() { memset(w,0,sizeof(w)); scanf("%d%d",&n,&m); for(int i=0;i
                        
                         >sx>>sy>>ex>>ey>>ch; man s; s.x=sx;s.y=sy;s.step=0; if(ch=='E')s.dir=0; if(ch=='S')s.dir=1; if(ch=='W')s.dir=2; if(ch=='N')s.dir=3; q.push(s); vis[sx][sy][s.dir]=1; bfs(); if(!flag)puts("-1"); return 0;}

View Code

转载于:https://www.cnblogs.com/jianrenfang/p/5774970.html

你可能感兴趣的文章