题解 P2385 【青铜莲花池】
顾z
2018-09-10 19:18:21
# [顾z](http://www.cnblogs.com/-guz/)
题目描述--->[p2385 青铜莲花池](https://www.luogu.org/problemnew/show/P2385)
## 分析
很明显了,题目告诉我们有八个方向,当然优先考虑**bfs**!
很简单的bfs,重点在于**考虑清楚8个方向**.
~~自己刚开始打错了 emmm~~
给大家上一个图.↓
**(假定m1为3,m2为2)**
对应加减的就是我们的原来的坐标.
然后就完了 emmmm
~~感觉写的不算太丑~~
---------------------代码--------------------
```cpp
#include<bits/stdc++.h>
#define IL inline
#define RI register int
IL void in(int &x)
{
int f=1;x=0;char s=getchar();
while(s>'9' or s<'0'){if(s=='-')f=-1;s=getchar();}
while(s>='0' and s<='9'){x=x*10+s-'0';s=getchar();}
x*=f;
}
int n,m,a,b,sx,sy,tx,ty;
int res[33][33];
bool vis[33][33];
int ax[10],ay[10];
struct cod{int x,y,step;};
IL int bfs()
{
std::queue<cod>q;
q.push((cod){sx,sy,0});
vis[sx][sy]=true;
while(!q.empty())
{
int x=q.front().x,y=q.front().y,cnt=q.front().step;
if(x==tx and y==ty)return cnt;
q.pop();
for(RI i=1;i<=8;i++)
{
int nx=x+ax[i],ny=y+ay[i];
if(nx<1 or nx>n or ny<1 or ny>m )continue;
if(vis[nx][ny]==true or res[nx][ny]==0 or res[nx][ny]==2)continue;
if(nx==tx and ny==ty)return cnt+1;
q.push((cod){nx,ny,cnt+1});
vis[nx][ny]=true;
}
}
}
main(void)
{
in(n),in(m),in(a),in(b);
for(RI i=1;i<=n;i++)
for(RI j=1;j<=m;j++)
{
in(res[i][j]);
if(res[i][j]==3)sx=i,sy=j;
if(res[i][j]==4)tx=i,ty=j;
}
if(a!=b)
{
ax[1]=a,ay[1]=b;
ax[2]=a,ay[2]=-b;
ax[3]=-a,ay[3]=b;
ax[4]=-a,ay[4]=-b;
ax[5]=b,ay[5]=a;
ax[6]=b,ay[6]=-a;
ax[7]=-b,ay[7]=a;
ax[8]=-b,ay[8]=-a;
}
printf("%d",bfs());
}
```