啊吧啊吧
by qiaozhipeng123 @ 2023-08-23 16:03:36
这段代码的转向和行走是分开处理的，比较好理解，改成这样就AC了，但不知道你那个为什么错
```cpp
#include<bits/stdc++.h>
using namespace std;
int n,m;
const int N=100;
int a[N][N];
struct re{
int x;
int y;
int d;
int step;
};
queue<re> q;
int fx[6][4]={{0,0,0},{1,2,3},{0,0,0},{-1,-2,-3},{0,0,0}};
int fy[6][4]={{0,0,0},{0,0,0},{-1,-2,-3},{0,0,0},{1,2,3}};
int ans=1e9;
bool vis[N][N][N];
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin>>a[i][j];
if(a[i][j]==1){
a[i][j-1]=a[i-1][j]=a[i-1][j-1]=1;
}
}
};
int sx,sy,zx,zy;
cin>>sx>>sy>>zx>>zy;
char c;
cin>>c;
if(sx==zx&&sy==zy){
cout<<0;
return 0;
}
if(a[sx][sy]==1||a[zx][zy]==1){
cout<<-1;
return 0;
}
int f;
if(c=='S') f=1;//下
if(c=='W') f=2;//左
if(c=='N') f=3;//上
if(c=='E') f=4;//右
vis[sx][sy][f]=1;
q.push((re){sx,sy,f,0});
while(!q.empty()){
re x=q.front();
q.pop();
if(x.x==zx&&x.y==zy){
cout<<x.step;
return 0;
}
// for(int i=1;i<=4;i++){
for(int j=0;j<3;j++){
int tx=x.x+fx[x.d][j];
int ty=x.y+fy[x.d][j];
if(a[tx][ty]==1||tx<1||tx>=n||ty<1||ty>=m) break;
if(vis[tx][ty][x.d]) continue;
q.push((re){tx,ty,x.d,x.step+1});
vis[tx][ty][x.d]=1;
// if(!vis[tx][ty][i]){
// if(x.d==i){//不转
// vis[tx][ty][i]=1;
// q.push((re){tx,ty,i,x.step+1});
// }
// if(abs(x.d-i)==1||abs(x.d-i)==3){//转一下
// vis[tx][ty][i]=1;
// q.push((re){tx,ty,i,x.step+2});
// }
// if(abs(x.d-i)==2){//转两下
// vis[tx][ty][i]=1;
// q.push((re){tx,ty,i,x.step+3});
// }
// }
// }
}
int ffx=x.d;
if(ffx-1==0) ffx=5;
if(!vis[x.x][x.y][ffx-1]) q.push((re){x.x,x.y,ffx-1,x.step+1}),vis[x.x][x.y][ffx-1]=1;
ffx=x.d;
if(ffx+1==5) ffx=0;
if(!vis[x.x][x.y][ffx+1]) q.push((re){x.x,x.y,ffx+1,x.step+1}),vis[x.x][x.y][ffx+1]=1;
}
cout<<-1;
return 0;
}
```
by liuyize549330 @ 2023-08-23 17:12:40
你检查一下，机器人不能在地图边缘上走，我的就是错这里
by Kingah @ 2023-08-27 18:33:01
```
#include <iostream>
#include <cstring>
using namespace std;
#define x first
#define y second
typedef pair<pair<int,int>, int> PII;
const int N = 55, M = N * N * 4;
int n, m;
PII q[M];
int g[N][N], dist[N][N][4];
bool vis[N][N][4];
int ix[4] = {-1, -1, 0, 0}, iy[4] = {-1, 0, -1, 0};
// 判断是否被阻拦
bool is_block(int xi, int yi){
for (int i = 0; i < 4; i ++){
int ga = xi+ ix[i], gb = yi + iy[i];
if (ga < 0 || ga >= n || gb < 0 || gb >= m) continue;
if (g[ga][gb] == 1) return true;
}
return false;
}
int bfs(int sx, int sy, int ex, int ey, char dir){
int hh = 0, tt = 0;
memset(dist, 0x3f, sizeof dist);
// 0N 1E 2S 3W
char cs[5] = "NESW";
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
for (int i = 0; i < 4; i ++)
if (dir == cs[i]){
q[tt] = {{sx, sy}, i};
dist[sx][sy][i] = 0;
vis[sx][sy][i] = true;
break;
}
while(hh <= tt){
auto u = q[hh ++];
int xi = u.x.x, yi = u.x.y;
int d = u.y;
if (xi == ex && yi == ey) {
int res = 0x3f3f3f3f;
for (int i = 0; i < 4; i ++)
res = min(res, dist[xi][yi][i]);
return res;
}
// 0 左转 -1 右转
for (int i = -1; i < 4; i ++){
int a = xi, b = yi, c = d;
if (i == 0){
c = d > 0 ? d - 1: 3;
}else if (i == -1){
c = d > 2 ? 0 : d + 1;
}else{
a = xi + dx[c] * i, b = yi + dy[c] * i;
if (a <= 0 || a >= n || b <= 0 || b >= m) continue;
if (is_block(a, b)) break;
}
if (vis[a][b][c]) continue;
vis[a][b][c] = true;
q[++ tt] = {{a, b}, c};
dist[a][b][c] = dist[xi][yi][d] + 1;
}
}
return -1;
}
int main(){
cin >> n >> m;
for (int i = 0; i < n; i ++)
for (int j = 0; j < m ; j ++)
cin >> g[i][j];
int sx, sy, ex, ey;
char dir;
cin >> sx >> sy >> ex >> ey >> dir;
cout << bfs(sx, sy, ex, ey, dir) << endl;
return 0;
}
```
by Kingah @ 2023-08-27 18:34:05
...
by liyuduan @ 2024-01-08 19:11:51
8:一开始就看自己的后面。[看这个](https://www.luogu.com.cn/discuss/743084)
by wanghaoyu120717 @ 2024-01-10 14:58:07