P1126 机器人搬重物

BFS+各种恶心的细节

题意描述

有一个(洛谷)公司，发明了一种机器人，用来搬题解，

题解储藏室是一个N*M的房间，其中某些地方有正方形的障碍物（注意：正方形四个顶点都是不能走的）

机器人每秒可以走1-3步，但只能沿直线走，求到达终点的最小时间。

看不懂请走传送门

算法分析

典型bfs，但恶心细节是真的多。

相比较于普通bfs，它多个什么呢：

1. 它是网格图，而不是点图。
2. 它是可以走1~3步的，而且花的时间一样多。
3. 它转弯是要时间的。

如果你解决了以上问题你就AC了。。。

网格图

既然它不是点阵图，那就把它变成点阵图。

具体方法如下：

void change(){
   for(int i=1;i<=n;i++)
     for(int j=1;j<=m;j++)
       if(s[i][j]) a[i-1][j]=a[i][j-1]=a[i-1][j-1]=a[i][j]=1;

还看不懂的话可以手玩几组数据。

花式步伐

bfs时多一个循环i=1~3即可（具体见下）

转弯

这个比较棘手，因为它我开了好几个数组：

1. **int ft[5]={0,1,4,2,3};//ft[i]表示顺时针排列各个方向的编号(上1 右4 下2 左3)

** 2. int fft[5]={0,1,3,4,2};//fft[i]表示数字i在ft[]数组中的下标 （1在第1个，2在第3个…）

3. int step[5]={0,1,2,1,0};//step[i]表示转到[顺时针转i次到达的那个方向]的最短次数

以上都是按顺时针标记。

1，3比较好理解，但2是个什么东东呢？

其实，2是必不可少的一部分，是1的索引。

例如转向时，你的方向是1（即上方），现在要顺时针转2下，你现在面向哪？又要转多少次呢？

显然，最少步数是step[2]=2,但要发现自己面向哪里，需要将1转化成自己在ft[]下标，

即fft[1]=1,再用ft[fft[1]+2]作为答案（这很明显，就不推了，但要注意以下，fft[]+n可能>4,所以要处理一下）

其余步骤

其实难点已经解决了，接下来是写给像我一样的蒟蒻们看的。

接下来开始bfs，用f[i][j]表示：走到（i,j）的最短步数。

最后输出f[终点x] [终点y]即可。（特判：如果终点就在起点，输出0）

如果f[终点x] [终点y]==0，则无解。

代码实现

此代码丧心病狂，看了 \(rp-=INF\)。

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <iostream>
#include <cmath>
#include <queue>
#define maxn 55
using namespace std;

int dx[5]={0,-1,1,0,0};
int dy[5]={0,0,0,-1,1};
int ft[5]={0,1,4,2,3};//上1,右4,下2,左3
int fft[5]={0,1,3,4,2};
int step[5]={0,1,2,1,0};

struct node{
   int x,y,t,time;
 };
 int n,m,f[maxn][maxn],a[maxn][maxn],s[maxn][maxn];
 int xbegin,ybegin,xend,yend,tbegin;
 queue<node>q;

void find_tbegin(){
   char z;
   cin>>z;
   if(z=='N') {tbegin=1;return;}
   if(z=='S') {tbegin=2;return;}
   if(z=='W') {tbegin=3;return;}
   if(z=='E') {tbegin=4;return;}
 }

void change(){
   for(int i=1;i<=n;i++)
     for(int j=1;j<=m;j++)
       if(s[i][j]) a[i-1][j]=a[i][j-1]=a[i-1][j-1]=a[i][j]=1;
 }

int main(){
   scanf("%d %d",&n,&m);
   for(int i=1;i<=n;i++){
     for(int j=1;j<=m;j++){
       scanf("%d",&s[i][j]);
     }
   }
   scanf("%d %d %d %d",&xbegin,&ybegin,&xend,&yend);
   find_tbegin();
   change();
   node first;
   first.x=xbegin;
   first.y=ybegin;
   first.t=tbegin;
   first.time=0;
   q.push(first);
   
   node now;
   while(!q.empty()){
     now=q.front();
     q.pop();
     for(int i=1;i<=4;i++){
       int zhuan=step[i];
       int tt=fft[now.t]+i;
       if(tt==5) tt=1;
       if(tt==6) tt=2;
       if(tt==7) tt=3;
       if(tt==8) tt=4;
       tt=ft[tt];

for(int j=1;j<=3;j++){
         int gx=now.x+dx[tt]*j;
         int gy=now.y+dy[tt]*j;
         int gt=now.time+zhuan+1;

if(gx<=0 || gx>=n || gy<=0 || gy>=m || (gx==xbegin&&gy==ybegin) || a[gx][gy]==1)
         break;

if((gt<f[gx][gy] || f[gx][gy]==0)){
           node p;
           p.x=gx;p.y=gy;
           p.t=tt;p.time=gt;
           f[gx][gy]=p.time;
           q.push(p);
         }
       }
     }
   }

if(f[xend][yend]==0 && (xbegin!=xend || ybegin!=yend)){
     printf("-1\n");
   }
   else{
     printf("%d\n",f[xend][yend]);
   }
   system("pause");
   return 0;
 }

结语

恶心的bfs