有可能你缺了这一点:
> 首先,这道题需要注意,障碍物是在格子上,而机器人是在格点上走。
我是这样写的:
```cpp
#include<bits/stdc++.h>
using namespace std;
struct robot
{
int x,y,d,step;
}p,t;
queue <robot> q;
int n,m,k,sx,sy,ex,ey,tx,ty,ans;
char d;
int f,g[55][55],dp[55][55][5];
bool flag;
int dir[4][2] = {1,0,0,1,-1,0,0,-1};
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
{
scanf("%d",&f);
if(f==1)
{
g[i][j]=1;
g[i-1][j]=1;
g[i][j-1]=1;
g[i-1][j-1]=1;
}
}
memset(dp,63,sizeof(dp));
ans= -1;
cin>>sx>>sy>>ex>>ey>>d;
p.x = sx;
p.y = sy;
if(d == 'S') p.d = 0;
else if(d == 'E') p.d = 1;
else if(d == 'N') p.d = 2;
else p.d = 3;
dp[sx][sy][p.d] = 0;
q.push(p);
while(!q.empty())
{
t = q.front();
if(t.x == ex && t.y == ey)
{
ans = t.step;
break;
}
q.pop();
//向前走一步
tx = t.x + dir[t.d][0];
ty = t.y + dir[t.d][1];
if(tx >= 1 && ty >= 1 && tx < n && ty < m && !g[tx][ty] && dp[tx][ty][t.d] > t.step+1)
{
p.x = tx;
p.y = ty;
p.d = t.d;
p.step = t.step + 1;
dp[tx][ty][p.d] = p.step;
q.push(p);
}
//向前走两步
tx = t.x;
ty = t.y;
flag = 0;
for(int i = 1; i <= 2; ++i)
{
tx += dir[t.d][0];
ty += dir[t.d][1];
if(tx < 1 || ty < 1 || tx >= n || ty >= m || g[tx][ty]) flag = 1;
}
if(!flag && dp[tx][ty][t.d] > t.step+1)
{
p.x = tx;
p.y = ty;
p.d = t.d;
p.step = t.step + 1;
dp[tx][ty][p.d] = p.step;
q.push(p);
}
//向前走三步
tx = t.x;
ty = t.y;
flag = 0;
for(int i = 1; i <= 3; ++i)
{
tx += dir[t.d][0];
ty += dir[t.d][1];
if(tx < 1 || ty < 1 || tx >= n || ty >= m || g[tx][ty]) flag = 1;
}
if(!flag && dp[tx][ty][t.d] > t.step+1)
{
p.x = tx;
p.y = ty;
p.d = t.d;
p.step = t.step + 1;
dp[tx][ty][p.d] = p.step;
q.push(p);
}
//左转
tx = t.x ;
ty = t.y;
p.d = (t.d + 1) % 4;
if(dp[tx][ty][p.d] > t.step+1)
{
p.x = tx;
p.y = ty;
p.step = t.step + 1;
dp[tx][ty][p.d] = p.step;
q.push(p);
}
//右转
tx = t.x ;
ty = t.y;
p.d = (t.d + 3) % 4;
if(dp[tx][ty][p.d] > t.step+1)
{
p.x = tx;
p.y = ty;
p.step = t.step + 1;
dp[tx][ty][p.d] = p.step;
q.push(p);
}
}
printf("%d\n",ans);
return 0;
}
```
码分奇怪,见谅
by ethanhyz @ 2022-11-05 11:51:06