题解：P9351 [JOI 2023 Final] Maze

绝世好题！

题意：给一个 r \times c 的网格图，有一些障碍物。每次操作可以打通一个 n \times n 的正方形，求将输入的起点和终点四联通的最小操作步数。

我们可以先思考一个 O(rcn^2) 的简单做法。

我们可以从起点开始 BFS，走到一个点可以：

• 走到与该格子四联通的一个非障碍物位置，花费 0 代价。
• 走到与该格子四联通的一个障碍物位置，花费 1 代价并直接传送到该格子所在的 n \times n 正方形中的任意一格。

我们发现瓶颈在于传送到 n \times n 正方形的任一格子这一步。

我们可以画一个图，看一下从一个格子传送一次最远能够走到哪里。最极端的情况就是我当前所在的格子和我要传送到的格子正好在这个正方形对角线的两端。因此，我们容易发现：我们能够传送到的点，恰好就是从当前格子走 n-1 步八联通的点。

想到这里，正解也就呼之欲出了。我们依然可以 01BFS，在每个节点存当前坐标，当前代价和还能走多少步八联通。复杂度为 O(rc)，代码如下：

#include<bits/stdc++.h>
#define int long long
#define endl '\n'
#define N 6000006
using namespace std;
int n,m,k,sx,sy,ex,ey;
vector<int> mp[N],vis[N];
struct Node{int x,y,dis,lef;};
deque<Node> dq;
char ch[N];
int dx[]={0,0,1,-1,1,1,-1,-1};
int dy[]={-1,1,0,0,1,-1,1,-1};
main()
{
    scanf("%lld%lld%lld%lld%lld%lld%lld",&n,&m,&k,&sx,&sy,&ex,&ey);
    for(int i=1;i<=n;i++)
    {
        mp[i].push_back(0),vis[i].push_back(0);
        scanf("%s",ch+1);
        for(int j=1;j<=m;j++)mp[i].push_back(ch[j]=='#'),vis[i].push_back(0);
    }
    dq.push_back({sx,sy,0,0});
    while(dq.size())
    {
        Node now=dq.front();dq.pop_front();
        if(vis[now.x][now.y])continue;
        if(now.x==ex&&now.y==ey)return printf("%lld\n",now.dis),0;
        vis[now.x][now.y]=1;
        if(now.lef)
        {
            for(int i=0;i<8;i++)
            {
                int tx=now.x+dx[i],ty=now.y+dy[i];
                if(tx>0&&ty>0&&tx<=n&&ty<=m&&!vis[tx][ty])
                    dq.push_back({tx,ty,now.dis,now.lef-1});
            }
        }
        else
        {
            for(int i=0;i<4;i++)
            {
                int tx=now.x+dx[i],ty=now.y+dy[i];
                if(tx>0&&ty>0&&tx<=n&&ty<=m&&!vis[tx][ty])
                {
                    if(mp[tx][ty])dq.push_back({tx,ty,now.dis+1,k-1});
                    else dq.push_front({tx,ty,now.dis,0});
                }
            }
        }
    }
    return 0;
}