已AC,但自测数据加上#8数据对比有问题 其实我并没有对
搜索初学蒻鸡,无法自解
本人代码如下
#include<bits/stdc++.h>
using namespace std;
char mp[302][302];
int mmp[302][302];
bool bj[302][302];
int d[100000][2],
dx[4]={-1,1,0,0},
dy[4]={0,0,-1,1};
int n,m;
int change(int &x,int &y)
{
for(int i=1; i<=n; i++)
{
for(int j=1; j<=m; j++)
{
if(!(i==x&&j==y))
{
if(mp[i][j]==mp[x][y])
{
x=i;
y=j;
return 0;
}
}
}
}
}
bool asd[26];
void bfs(int x,int y){
int head=0,tail=1;
d[tail][0]=x,d[tail][1]=y;
bj[x][y]=true;
do{
head++;
int xn=d[head][0],yn=d[head][1];
if(mp[xn][yn]>='A'&&mp[xn][yn]<='Z'){
int z=mmp[xn][yn];
change(xn,yn);
mmp[xn][yn]=z;
}
for(int i=0;i<4;i++){
int nx=xn+dx[i],ny=yn+dy[i];
if((mp[nx][ny]!='#')&&(!bj[nx][ny])){
bj[nx][ny]=true;
tail++;
d[tail][0]=nx;
d[tail][1]=ny;
mmp[nx][ny]=mmp[xn][yn]+1;
if(mp[nx][ny]=='=') {
cout << mmp[nx][ny];
return ;
}
}
}
}while(head<tail);
}
int main(){
cin >> n >> m;
int x,y;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
char c; cin >> c;
if(c=='@') x=i,y=j;
mp[i][j]=c;
}
}
bfs(x,y);
return 0;
}
#8的数据如下
8 6
###=##
#..W.#
#....#
##@..#
#....#
#....#
#..W.#
######
依照本人设置的入队顺序 dx[4]={-1,1,0,0}, dy[4]={0,0,-1,1}; 即 ↓ ↑ ← →的入队顺序 是没有问题的,跑出来的值图是酱紫:
000500
032440
021230
000120
021230
032340
043440
000000
完全没有问题,但如果把入队顺序换一下,如 dx[4]={1,-1,0,0}, dy[4]={0,0,-1,1};即 变为 ↑ ↓ ← →的入队顺序,跑出来就是:
000400
032340
021230
000120
021230
032340
043340
000000
可见,若非恰好在此数据下程序先从下方入队了传送门,我的程序会直接无视上方的传送门在第四步的时候就到达终点,不知道是什么问题....望各位大佬帮忙看看
┭┮﹏┭┮