自动搬运

查看原文

来自洛谷，原作者为

	封禁用户 None

搬运于2025-08-24 23:02:31，当前版本为作者最后更新于2024-08-24 12:21:45，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

设地图大小为 $s=nm$，传送入口为 $P_x$，出口为 $Q_i$，起点为 $Q_0$，终点为 $T_y$，$\to$ 为最短路径，$\Rightarrow$ 为传送。

很明显，最短路径只能是以下中的一种：

• $Q_0 \to T_y$；
• $Q_0 \to P_x \Rightarrow Q_1 \to T_y$；
• $Q_0 \to P_x \Rightarrow Q_1 \to P_x \Rightarrow Q_2 \to T_y$；
• $Q_0 \to P_x \Rightarrow Q_1 \to P_x \Rightarrow Q_2 \to P_x \Rightarrow Q_3 \to T_y$；
• ………………………………………………………………………
• $Q_0 \to P_x \Rightarrow Q_1 \to P_x \Rightarrow Q_2 \to P_x \Rightarrow Q_3 \to \ldots \Rightarrow Q_n \to T_y$。

因此，我们要求出 $Q_i \to P_x$ 的长度，并以此求出 $Q_0 \to \ldots \to Q_i \to T_y$ 的长度。

---

很明显，求 $Q_i \to P_x$ 的长度时，$(q+1)$ 遍 BFS 是不可取的。然而，由于这 $(q+1)$ 遍 BFS 的终点都是 $P_x$，我们可以以 $P_x$ 为起点反向进行 BFS，这样就可以在 $O(s)$ 内求出 $Q_i \to P_x$ 的长度了。

举个例子：

$\color{red} Q_2\color{black}/\color{blue} P_x$	$.$	$\color{red} Q_3\color{black}/\color{red} Q_4$	$\#$	$\color{red} Q_5$
$\#$	$\#$	$\#$
$.$		$\color{red} Q_6$	$.$	$\color{blue} P_x$
$\#$		$.$	$\#$
$\color{red} Q_1$	$.$		$.$	$\color{green} Q_0$

初始状态：

$0$			$\#$
$\#$	$\#$	$\#$
				$0$
$\#$			$\#$
		$\color{white}.$

最终状态（$6$ 轮 BFS 后）：

$0$	$1$	$2$	$\#$
$\#$	$\#$	$\#$
		$2$	$1$	$0$
$\#$		$3$	$\#$
$6$	$5$	$4$	$5$	$6$

因此 $Q_{[0,6]} \to P_x$ 的长度分别为 $6,6,0,2,2,+\infty,2$（$Q_5$ 无法到达 $P_x$），$Q_0 \to Q_{[0,6]}$（走传送门）的长度分别为 $0,6,12,12,14,16,+\infty$（$Q_6$ 无法通过这一方式到达，因为 $Q_5$ 无法到达 $P_x$）。

---

求 $Q_0 \to \ldots \to Q_i \to T_y$ 的长度时，我们仍然可以 BFS，对每个可能的最短路径长度 BFS 一轮即可。当目前长度等于 $Q_0 \to Q_i$（走传送门）的长度，且 $Q_i$ 还没有入队时，我们要将 $Q_i$ 入队。

我们继续使用上面的例子。

初始状态：

			$\#$
$\#$	$\#$	$\#$
$\#$			$\#$
				$0$

$6$ 轮 BFS 后：

			$\#$
$\#$	$\#$	$\#$
		$4$	$5$	$6$
$\#$		$3$	$\#$
$4$	$3$	$2$	$1$	$0$

在第 $6$ 轮 BFS 中，由于 $Q_0 \to Q_1$（走传送门）的长度为 $6$，此时 $Q_1$ 应当入队。但 $Q_1$ 在此之前已经入队，因此不再将 $Q_1$ 入队。

在第 $7 \sim 11$ 轮 BFS 中，虽然此时没有新结点入队，但不能结束 BFS，因为 $Q_2 \sim Q_5$ 还没有入队（$Q_6$ 走传送门无法到达，不需要入队）。

$12$ 轮 BFS 后：

$12$		$12$	$\#$
$\#$	$\#$	$\#$
		$4$	$5$	$6$
$\#$		$3$	$\#$
$4$	$3$	$2$	$1$	$0$

$Q_2,Q_3$ 入队。

$13$ 轮 BFS 后：

$12$	$13$	$12$	$\#$
$\#$	$\#$	$\#$
		$4$	$5$	$6$
$\#$		$3$	$\#$
$4$	$3$	$2$	$1$	$0$

在第 $14$ 轮 BFS 中，$Q_4$ 应当入队，但它在此之前已经入队。

$16$ 轮 BFS 后：

$12$	$13$	$12$	$\#$	$16$
$\#$	$\#$	$\#$
		$4$	$5$	$6$
$\#$		$3$	$\#$
$4$	$3$	$2$	$1$	$0$

在第 $16$ 轮 BFS 中，$Q_5$ 入队。

$Q_6$ 不需要入队，并且从第 $17$ 轮 BFS 开始不再有新结点入队，因此 BFS 结束。

---

然而，上面的做法会 TLE，因为路径长度可以达到 $qs=10^{12}$（因此答案要开 long long）。

优化很简单：当队列内没有结点时，将当前处理的最短路径长度直接设为使得下一个 $Q_i$ 入队的最短路径长度。例如，在上面的例子中，当第 $6$ 轮 BFS 结束后，可以直接跳到第 $12$ 轮 BFS，跳过第 $7 \sim 11$ 轮 BFS。

最终的时间复杂度为 $O(s)$，空间复杂度为 $O(s)$。

---

上面例子对应的输入输出数据如下：

输入：

0
5 5
...#.
#####
.#...
##.##
.....
5 5 2 6
3 5
1 1
5 1
1 1
1 3
1 3
1 5
3 3

输出：

12 13 12 -1 16
-1 -1 -1 -1 -1
-1 -1 4 5 6
-1 -1 3 -1 -1
4 3 2 1 0

---

AC Code：

#include <bits/stdc++.h>
#define int long long
using namespace std;
char s[1012][1012];
int ans[1012][1012];
int res[1012][1012];
bool alr[1012][1012];
int px[1000012],py[1000012],qx[1000012],qy[1000012];
int fir[1000012];
signed main()
{
    memset(s,'#',sizeof s);
    memset(ans,-1,sizeof ans);
    memset(res,-1,sizeof res);
    memset(alr,0,sizeof alr);
    ios::sync_with_stdio(0);
    int o;
    cin>>o;
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            cin>>s[i][j];
    int sx,sy,p,qq,tx,ty;
    cin>>sx>>sy>>p>>qq;
    ans[sx][sy]=0;
    if(o) cin>>tx>>ty;
    for(int i=1;i<=p;i++)
        cin>>px[i]>>py[i];
    for(int i=1;i<=qq;i++)
        cin>>qx[i]>>qy[i];
    queue<pair<int,int> > q;
    int cnt=0;
    for(int i=1;i<=p;i++)
    {
        q.push(make_pair(px[i],py[i]));
        alr[px[i]][py[i]]=true;
    }
    while(!q.empty())
    {
        int ct=q.size();
        while(ct--)
        {
            pair<int,int> u=q.front();
            q.pop();
            res[u.first][u.second]=cnt;
            if(s[u.first][u.second+1]=='.'&&!alr[u.first][u.second+1])
            {
                alr[u.first][u.second+1]=true;
                q.push(make_pair(u.first,u.second+1));
            }
            if(s[u.first+1][u.second]=='.'&&!alr[u.first+1][u.second])
            {
                alr[u.first+1][u.second]=true;
                q.push(make_pair(u.first+1,u.second));
            }
            if(s[u.first][u.second-1]=='.'&&!alr[u.first][u.second-1])
            {
                alr[u.first][u.second-1]=true;
                q.push(make_pair(u.first,u.second-1));
            }
            if(s[u.first-1][u.second]=='.'&&!alr[u.first-1][u.second])
            {
                alr[u.first-1][u.second]=true;
                q.push(make_pair(u.first-1,u.second));
            }
        }
        cnt++;
    }
    fir[1]=res[sx][sy];
    for(int i=2;i<=qq;i++)
    {
        if(res[qx[i-1]][qy[i-1]]==-1||fir[i-1]==-1) fir[i]=-1;
        else fir[i]=fir[i-1]+res[qx[i-1]][qy[i-1]];
    }
    fir[qq+1]=-1;
    memset(alr,0,sizeof alr);
    q.push(make_pair(sx,sy));
    alr[sx][sy]=true;
    cnt=0;
    int now=1;
    while(!q.empty()||fir[now]!=-1)
    {
        if(q.empty()) cnt=fir[now];
        while(fir[now]==cnt)
        {
            if(!alr[qx[now]][qy[now]])
            {
                q.push(make_pair(qx[now],qy[now]));
                alr[qx[now]][qy[now]]=true;
            }
            now++;
        }
        int ct=q.size();
        while(ct--)
        {
            pair<int,int> u=q.front();
            q.pop();
            ans[u.first][u.second]=cnt;
            if(s[u.first][u.second+1]=='.'&&!alr[u.first][u.second+1])
            {
                alr[u.first][u.second+1]=true;
                q.push(make_pair(u.first,u.second+1));
            }
            if(s[u.first+1][u.second]=='.'&&!alr[u.first+1][u.second])
            {
                alr[u.first+1][u.second]=true;
                q.push(make_pair(u.first+1,u.second));
            }
            if(s[u.first][u.second-1]=='.'&&!alr[u.first][u.second-1])
            {
                alr[u.first][u.second-1]=true;
                q.push(make_pair(u.first,u.second-1));
            }
            if(s[u.first-1][u.second]=='.'&&!alr[u.first-1][u.second])
            {
                alr[u.first-1][u.second]=true;
                q.push(make_pair(u.first-1,u.second));
            }
        }
        cnt++;
    }
    if(o) cout<<ans[tx][ty];
    else
    {
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=m;j++)
                cout<<ans[i][j]<<' ';
            cout<<endl;
        }
    }
    return 0;
}