题意:给你一张图,"."表示能走,"#表示不能走,步行可以向四周四个方向移动一个单位,使用魔法可以移动到周围\(5\)Ｘ\(5\)的空地,问能否从起点都早终点,并求最少使用多少次魔法.

题解:明显是用BFS,但是我们要能步行就步行,尽量少使用魔法,所以我们可以用deque来存状态,将步行的状态放在前面,魔法的放在后面,这样就能保证优先步行,用结构体来表示状态即可.

代码:

struct misaka{
    int x,y;
    int cnt;
}e;

int n,m;
int sx,sy;
int ex,ey;
char g[2000][2000];
bool st[2000][2000];
int dx[4]={0,0,1,-1},dy[4]={1,-1,0,0};
int ans=INF;

void bfs(){
deque<misaka> q;
q.pb({sx,sy,0});

while(!q.empty()){
    auto tmp=q.front();
    q.pop_front();

    int x=tmp.x;
    int y=tmp.y;
    int cnt=tmp.cnt;

    if(x==ex && y==ey){
        ans=cnt;
        return;
    }

    if(st[x][y]) continue;
    st[x][y]=true;

    for(int i=0;i<4;++i){
        int tx=x+dx[i];
        int ty=y+dy[i];

        if(tx<1 || tx>n || ty<1 || ty>m  || g[tx][ty]=='#') continue;
        q.pf({tx,ty,cnt});
    }
    for(int i=x-2;i<=x+2;++i){
        for(int j=y-2;j<=y+2;++j){
            if(i<1 || i>n || j<1 || j>m  || g[i][j]=='#') continue;
            q.pb({i,j,cnt+1});
        }
    }
}
}

int main() {
    //ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    n=read();
    m=read();
    sx=read();
    sy=read();
    ex=read();
    ey=read();
for(int i=1;i<=n;++i){
    scanf("%s",g[i]+1);
}

bfs();

if(ans==INF) puts("-1");
else printf("%d\n",ans);

return 0;
}