做了两天,就是不AC
如果正着搜就只能80分,不懂为什么
倒着搜的话倒数第二个点WA了
代码:
#include<iostream>
#include<queue>
#define fffff 3005
using namespace std;
struct E{
int x,y,step;
}q[fffff];
int vis[fffff][fffff];
int dx[4]={0,0,-1,1};
int dy[4]={1,-1,0,0};
int n,m,sx,sy,ex,ey,head=0,tail=1;
char map[fffff][fffff];
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
{
cin>>map[i][j];
if(map[i][j]=='d')
{
sx=i;
sy=j;
}
if(map[i][j]=='m')
{
ex=i;
ey=j;
}
}
q[1].x=sx;
q[1].y=sy;
q[1].step=0;
vis[sx][sy]=1;
while(head<tail)
{
head++;
for(int i=0;i<4;i++)
{
int nx=q[head].x+dx[i];
int ny=q[head].y+dy[i];
if(ex==nx&&ny==ey)
{
cout<<q[head].step+1;
return 0;
}
//if(nx>=0&&ny>=0&&nx<n&&ny<m&&!vis[nx][ny]&&map[nx][ny]!='#')
if(nx<=0||ny<=0||nx>n||ny>m||vis[nx][ny]||map[nx][ny]=='#') continue;
{
vis[nx][ny]=1;
tail++;
q[tail].x=nx;
q[tail].y=ny;
q[tail].step=q[head].step+1;
}
}
}
cout<<"No Way!";
return 0;
}