题解 P2385 【青铜莲花池】

2018-09-10 19:18:21


顾z

题目描述--->p2385 青铜莲花池

分析

很明显了,题目告诉我们有八个方向,当然优先考虑bfs!

很简单的bfs,重点在于考虑清楚8个方向.

自己刚开始打错了 emmm

给大家上一个图.↓

(假定m1为3,m2为2)

对应加减的就是我们的原来的坐标.

然后就完了 emmmm

感觉写的不算太丑

---------------------代码--------------------

#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());
}