P1126 机器人搬重物（BFS）
程序员文章站
2022-06-12 09:54:37
...
题目描述
机器人移动学会（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
思路：此题带方向还有步数，比较恶心，所以判重的时候要用三维数组判重（带着方向），并且注意！边界的线是不能走的！！
然后常规BFS即可.噢 对了 记得把格子图转换为点图
#include<bits/stdc++.h>
#define MAXN 100000
using namespace std;
typedef long long ll;
ll M[55][55],n,m,a,b,c,d;
char str;
struct Why
{
ll x,y,num;
char st;
Why(ll a,ll b,ll c,char s)
{
x=a;
y=b;
num=c;
st=s;
}
};
bool R[55][55][5]; //判重
ll bfs(ll x1,ll y1,ll x2,ll y2,char s)
{
queue<Why>A;
A.push(Why(x1,y1,0,s));
if(s=='S')
R[x1][y1][2]=1;
else if(s=='N')
R[x1][y1][1]=1;
else if(s=='W')
R[x1][y1][3]=1;
else if(s=='E')
R[x1][y1][4]=1;
while(!A.empty())
{
Why K=A.front();
A.pop();
//cout<<K.x<<" "<<K.y<<" "<<K.num<<" "<<K.st<<endl;
if(K.x==x2&&K.y==y2)
{
cout<<K.num<<endl;
return 0;
}
if(K.st=='E')
{
if(R[K.x][K.y][1]==0) //方向的转变
{
A.push(Why(K.x,K.y,K.num+1,'N'));
R[K.x][K.y][1]=1;
}
if(R[K.x][K.y][2]==0)
{
A.push(Why(K.x,K.y,K.num+1,'S'));
R[K.x][K.y][2]=1;
}
if(R[K.x][K.y+1][4]==0&&K.x>1&&K.x<n&&K.y+1>1&&K.y+1<m&&M[K.x][K.y+1]==0) //步数的转变
{
A.push(Why(K.x,K.y+1,K.num+1,'E'));
R[K.x][K.y+1][4]=1;
}
if(R[K.x][K.y+2][4]==0&&K.x>1&&K.x<n&&K.y+2>1&&K.y+2<m&&M[K.x][K.y+2]==0&&M[K.x][K.y+1]==0)
{
A.push(Why(K.x,K.y+2,K.num+1,'E'));
R[K.x][K.y+2][4]=1;
}
if(R[K.x][K.y+3][4]==0&&K.x>1&&K.x<n&&K.y+3>1&&K.y+3<m&&M[K.x][K.y+3]==0&&M[K.x][K.y+2]==0&&M[K.x][K.y+1]==0)
{
A.push(Why(K.x,K.y+3,K.num+1,'E'));
R[K.x][K.y+3][4]=1;
}
}
else if(K.st=='N')
{
if(R[K.x][K.y][3]==0)
{
A.push(Why(K.x,K.y,K.num+1,'W'));
R[K.x][K.y][3]=1;
}
if(R[K.x][K.y][4]==0)
{
A.push(Why(K.x,K.y,K.num+1,'E'));
R[K.x][K.y][4]=1;
}
if(R[K.x-1][K.y][1]==0&&K.x-1>1&&K.x-1<n&&K.y>1&&K.y<m&&M[K.x-1][K.y]==0)
{
A.push(Why(K.x-1,K.y,K.num+1,'N'));
R[K.x-1][K.y][1]=1;
}
if(R[K.x-2][K.y][1]==0&&K.x-2>1&&K.x-2<n&&K.y>1&&K.y<m&&M[K.x-2][K.y]==0&&M[K.x-1][K.y]==0)
{
A.push(Why(K.x-2,K.y,K.num+1,'N'));
R[K.x-2][K.y][1]=1;
}
if(R[K.x-3][K.y][1]==0&&K.x-3>1&&K.x-3<n&&K.y>1&&K.y<m&&M[K.x-3][K.y]==0&&M[K.x-2][K.y]==0&&M[K.x-1][K.y]==0)
{
A.push(Why(K.x-3,K.y,K.num+1,'N'));
R[K.x-3][K.y][1]=1;
}
}
else if(K.st=='W')
{
if(R[K.x][K.y][2]==0)
{
A.push(Why(K.x,K.y,K.num+1,'S'));
R[K.x][K.y][2]=1;
}
if(R[K.x][K.y][1]==0)
{
A.push(Why(K.x,K.y,K.num+1,'N'));
R[K.x][K.y][1]=1;
}
if(R[K.x][K.y-1][3]==0&&K.x>1&&K.x<n&&K.y-1>1&&K.y-1<m&&M[K.x][K.y-1]==0)
{
A.push(Why(K.x,K.y-1,K.num+1,'W'));
R[K.x][K.y-1][3]=1;
}
if(R[K.x][K.y-2][3]==0&&K.x>1&&K.x<n&&K.y-2>1&&K.y-2<m&&M[K.x][K.y-2]==0&&M[K.x][K.y-1]==0)
{
A.push(Why(K.x,K.y-2,K.num+1,'W'));
R[K.x][K.y-2][3]=1;
}
if(R[K.x][K.y-3][3]==0&&K.x>1&&K.x<n&&K.y-3>1&&K.y-3<m&&M[K.x][K.y-3]==0&&M[K.x][K.y-2]==0&&M[K.x][K.y-1]==0)
{
A.push(Why(K.x,K.y-3,K.num+1,'W'));
R[K.x][K.y-3][3]=1;
}
}
else if(K.st=='S')
{
if(R[K.x][K.y][3]==0)
{
A.push(Why(K.x,K.y,K.num+1,'W'));
R[K.x][K.y][3]=1;
}
if(R[K.x][K.y][4]==0)
{
A.push(Why(K.x,K.y,K.num+1,'E'));
R[K.x][K.y][4]=1;
}
if(R[K.x+1][K.y][2]==0&&K.x+1>1&&K.x+1<n&&K.y>1&&K.y<m&&M[K.x+1][K.y]==0)
{
A.push(Why(K.x+1,K.y,K.num+1,'S'));
R[K.x+1][K.y][2]=1;
}
if(R[K.x+2][K.y][2]==0&&K.x+2>1&&K.x+2<n&&K.y>1&&K.y<m&&M[K.x+2][K.y]==0&&M[K.x+1][K.y]==0)
{
A.push(Why(K.x+2,K.y,K.num+1,'S'));
R[K.x+2][K.y][2]=1;
}
if(R[K.x+3][K.y][2]==0&&K.x+3>1&&K.x+3<n&&K.y>1&&K.y<m&&M[K.x+3][K.y]==0&&M[K.x+2][K.y]==0&&M[K.x+1][K.y]==0)
{
A.push(Why(K.x+3,K.y,K.num+1,'S'));
R[K.x+3][K.y][2]=1;
}
}
}
cout<<-1<<endl;
return 0;
}
int main()
{
ios::sync_with_stdio(false);
cin>>n>>m;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
{
cin>>a;
if(a==1) //转换为点图
{
M[i][j]=a;
M[i+1][j]=a;
M[i][j+1]=a;
M[i+1][j+1]=a;
}
}
n++;
m++;
// cout<<endl;
/* for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
cout<<M[i][j]<<" ";
}
cout<<endl;
}*/
cin>>a>>b>>c>>d>>str;
a++;b++;c++;d++;
bfs(a,b,c,d,str);
return 0;
}
上一篇： 深入理解php、jsp和asp的区别
下一篇： java批量将多文件打包成zip格式