LuoguP1126 机器人搬重物（BFS）

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

题目链接：https://www.luogu.org/problemnew/show/P1126

思路：很不错的搜索题，用BFS，虐了我1天多才A掉 QAQ，细节很多。

1.每个状态包含行、列、方向、步数。

2.需要将格点图转换为点图。

3.注意边界不能走。

4.最后是折磨了大半天的，救赎最后输入的字符，我最开始是写的scanf("%d%d%d%d%c",&sr,&sc,&er,&ec,&d)。我一直在找算法部分的bug，怎么也没想到竟然是它没有读到输入的字符，而读的是空格。因为scanf虽然在读数据会吃掉空格和换行，但只有scanf读char时不会吃掉空格和换行，虽然以前碰到过一次，但还是没意识到啊...解决办法是在%c前加一个空格就行，吸取教训了，血的教训。

AC代码如下：

#include<cstdio>
#include<queue>
#include<iostream>
using namespace std; struct cur{
int r,c,dir,step;
}tmp;
queue<cur> q;
int gr[][]={{-,-,-},{,,},{,,},{,,}};
int gc[][]={{,,},{,,},{,,},{-,-,-}};
int n,m,sr,sc,er,ec;
int a[][];
bool vis[][][]; void bfs(){
q.push(tmp);
while(!q.empty()){
cur now=q.front();q.pop();
int nr=now.r,nc=now.c,nd=now.dir,ns=now.step;
if(nr==er&&nc==ec){
printf("%d\n",ns);
return;
}
for(int i=;i<;i++){
int rr=nr+gr[nd][i],cc=nc+gc[nd][i];
if(rr<=||cc<=||rr>=n||cc>=m||a[rr][cc])
break;
if(!vis[rr][cc][nd]){
tmp.r=rr,tmp.c=cc,tmp.dir=nd,tmp.step=ns+;
vis[rr][cc][nd]=true;
q.push(tmp);
}
}
for(int i=-;i<=;i+=){
tmp.r=nr,tmp.c=nc;
int dd=nd+i;
if(dd==)dd=;
if(dd==-)dd=;
tmp.dir=dd;
tmp.step=ns+;
if(!vis[nr][nc][dd]){
vis[nr][nc][dd]=true;
q.push(tmp);
}
}
}
printf("-1\n");
} int main(){
int x;
char d;
scanf("%d%d",&n,&m);
for(int i=;i<=n;i++)
for(int j=;j<=m;j++){
scanf("%d",&x);
if(x)
a[i][j]=a[i-][j]=a[i-][j-]=a[i][j-]=;
}
scanf("%d%d%d%d",&sr,&sc,&er,&ec);
scanf(" %c",&d);
if(a[er][ec]){
printf("-1\n");
return ;
}
tmp.r=sr,tmp.c=sc;
switch(d){
case 'N':tmp.dir=;break;
case 'E':tmp.dir=;break;
case 'S':tmp.dir=;break;
case 'W':tmp.dir=;
}
tmp.step=;
vis[sr][sc][tmp.dir]=true;
bfs();
return ;
}