机器人移动学会（RMI）现在正尝试用机器人搬运物品。机器人的形状是一个直径 1.6 米的球。在试验阶段，机器人被用于在一个储藏室中搬运货物。储藏室是一个N×M 的网格，有些格子为不可移动的障碍。机器人的中心总是在格点上，当然，机器人必须在最短的时间内把物品搬运到指定的地方。机器人接受的指令有：
向前移动 1 步（Creep）；向前移动 2 步（Walk）；向前移动 3 步（Run）；向左转（Left）；向右转（Right）。
每个指令所需要的时间为 1 秒。请你计算一下机器人完成任务所需的最少时间。
输入格式
第一行为两个正整数 N,M (1≤N,M≤50)N,M (1≤N,M≤50)，下面 N 行是储藏室的构造，0 表示无障碍，1 表示有障碍，数字之间用一个空格隔开。接着一行有 4 个整数和 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
输出
12
输入
20 20
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0
0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 1 0 0 1 1 1 0 0 0 0 0 0 0 1 0 0 0
0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0
0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0
0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 1 0 0 0 0 1 0 1 0 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 0
0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 1 1 1 0 1 1 0 0 1 1 1 0 1 1 1
0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 1 0
0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0
0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0
0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0
0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
19 4 15 17 E
输出
33
输入
6 7
0 0 0 0 0 0 0
0 0 0 0 1 0 0
0 0 1 0 0 0 0
0 0 1 0 0 0 0
0 0 0 0 0 1 0
0 0 0 0 0 0 0
1 1 1 6 E
输出
11
思路：1.机器人有形状，所以不能看成一个点，观察题目给我们的图，知道01图要转换一次，在新的图里以1为右下角的正方形都是1；
2.接下来搜索，按照一个点往东南西北的走时的坐标变换，以及对应坐标变化的时间和方向（如下），在这里我把左右转和前移结合起来，比如左转后前移一格，或者向后转前移两格。
3.有点bfs的味道又混着dfs，主要这道题是bfs题，但是纯bfs我真想不出来。
int dx[]={-1,-2,-3,1,2,3,0,0,0,0,0,0};
int dy[]={0,0,0,0,0,0,1,2,3,-1,-2,-3};
int time1[4][12]={{2,2,2,2,2,2,1,1,1,3,3,3},
{3,3,3,1,1,1,2,2,2,2,2,2},
{2,2,2,2,2,2,3,3,3,1,1,1},
{1,1,1,3,3,3,2,2,2,2,2,2}};
int bfx[4][12]= {{3,3,3,1,1,1,0,0,0,2,2,2},
{2,2,2,0,0,0,-1,-1,-1,1,1,1},
{1,1,1,-1,-1,-1,-2,-2,-2,0,0,0},
{0,0,0,-2,-2,-2,-3,-3,-3,-1,-1,-1}};
注意：1.机器人，所以不能贴边走，会碰到储物室的墙壁
2.向前走两步或者三步的时候要特别判断一下，小心跳箱子
AC code
#include
#include
#include
using namespace std;
struct PII
{
int f,s,t1;
};
PII q[25001];
int g1[51][51]; //记录原图
int g2[51][51]; //记录真实的点图
int st[51][51]; //记录每个点的状态
int time2[51][51]; //记录到每个点的时间
int n,m;
int s1,e1,s2,e2;
char bf1;
int bf2;
void bfs(int x,int y,int z)
{
int dx[]={-1,-2,-3,1,2,3,0,0,0,0,0,0};
int dy[]={0,0,0,0,0,0,1,2,3,-1,-2,-3};
int time1[4][12]={{2,2,2,2,2,2,1,1,1,3,3,3},{3,3,3,1,1,1,2,2,2,2,2,2},{2,2,2,2,2,2,3,3,3,1,1,1},{1,1,1,3,3,3,2,2,2,2,2,2}};
int bfx[4][12]= {{3,3,3,1,1,1,0,0,0,2,2,2},{2,2,2,0,0,0,-1,-1,-1,1,1,1},{1,1,1,-1,-1,-1,-2,-2,-2,0,0,0},{0,0,0,-2,-2,-2,-3,-3,-3,-1,-1,-1}};
time2[x][y]=0;
q[0].f=x,q[0].s=y,q[0].t1=z;
int tt=0,ll=0;
while(ll<=tt)
{
PII t=q[ll++];
//printf("%d %d %d\n",t.f,t.s,time2[t.f][t.s]);
//printf("\n");
for(int i=0;i<12;i++)
{
int a=t.f+dx[i],b=t.s+dy[i],dir=t.t1+bfx[t.t1][i];
if(a<1||b<1||a>=n||b>=m) continue;
if(g2[a][b]==1) continue;
//开始特殊判断
if(st[a][b]==1&&time2[a][b]<=time2[t.f][t.s]+time1[t.t1][i]) continue;
if(g2[a][b]==0&&dx[i]==3&&(g2[a-1][b]==1||g2[a-2][b]==1)) continue;
else if(g2[a][b]==0&&dx[i]==2&&g2[a-1][b]==1) continue;
else if(g2[a][b]==0&&dx[i]==-3&&(g2[a+1][b]==1||g2[a+2][b]==1)) continue;
else if(g2[a][b]==0&&dx[i]==-2&&g2[a+1][b]==1) continue;
else if(g2[a][b]==0&&dy[i]==3&&(g2[a][b-1]==1||g2[a][b-2]==1)) continue;
else if(g2[a][b]==0&&dy[i]==2&&g2[a][b-1]==1) continue;
else if(g2[a][b]==0&&dy[i]==-3&&(g2[a][b+1]==1||g2[a][b+2]==1)) continue;
else if(g2[a][b]==0&&dy[i]==-2&&g2[a][b+1]==1) continue;
st[a][b]=1;
q[++tt].f=a,q[tt].s=b,q[tt].t1=dir;
time2[a][b]=time2[t.f][t.s]+time1[t.t1][i];
//printf("%d %d %d\n",a,b,time2[a][b]);
}
}
}
int main()
{
cin>>n>>m;
memset(g2,0,sizeof g2);//初始化数组
memset(time2,-1,sizeof time2);//初始化数组
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
cin>>g1[i][j];
if(g1[i][j]==1) //构造新图
{
g2[i][j]=1,g2[i-1][j]=1,g2[i][j-1]=1,g2[i-1][j-1]=1;
}
}
}
//printf("----------------------\n");
//for(int i=0;i<=n;i++)
//{
//for(int j=0;j<=m;j++)
//{
// printf("%d ",g2[i][j]);
//}
//printf("\n");
//}
cin>>s1>>e1>>s2>>e2>>bf1;
if(bf1=='E') bf2=0;
else if(bf1=='S') bf2=1;
else if(bf1=='W') bf2=2;
else bf2=3;
st[s1][e1]=1;
bfs(s1,e1,bf2);
if(time2[s2][e2]>-1) cout< else cout<<"-1"; return 0; } 精彩内容
您阅读本篇文章共花了：
发表评论