P1023 · OFFICIAL SOLUTION

P1023 迢迢寻故人官方题解

Gioush OJ · P1023 迢迢寻故人

迢迢寻故人

【题目简述】

在 $n\times m$ 的网格中，从 $[1,1]$ 走到 $[n,m]$ ，每一步可以四联通移动且允许重复经过格子。设经过数值的集合为 $S$ ，求 $\operatorname{mex}(S)$ 的最小值。

【数据点 1∼41\sim41∼4】

【题目描述】

枚举答案 $k$ ，暂时删除所有数值为 $k$ 的格子，再判断起点与终点能否四联通。

【解法】

第一次可以绕开 $k$ 时，答案就是 $k$ 。此前所有更小数值都无法绕开，而路径允许重复经过格子，因此只要仍在同一连通区域中，路线可以依次经过它们。

【复杂度分析】

单次 BFS 为 $\mathcal{O}(nm)$ ，直接枚举为 $\mathcal{O}(nm(n+m))$ 。

【数据点 5∼125\sim125∼12】

【同值屏障】

若同一行所有数相等，从第一行走到第 $n$ 行的任意路线都必须经过每一行；这一档的答案就是行代表值集合的 $\operatorname{mex}$ 。当 $\min(n,m)=1$ 时同理，必须经过整条线。

【Hint】

一个数值是否一定出现，取决于它对应的格子能否把起点与终点分隔开。

【正解】

【障碍墙】

固定数值 $k$ ，将所有值为 $k$ 的格子记为 $B_k$ 。把下边界与左边界合称为 $A$ ，把上边界与右边界合称为 $B$ 。若 $B_k$ 的某个八联通块同时接触 $A,B$ ，称它为一堵障碍墙。

【关键结论】

起点能够绕开数值 $k$ 到达终点，当且仅当不存在数值 $k$ 的障碍墙。

【证明】

先取一条连接 $[1,1]$ 与 $[n,m]$ 的最短四联通格路 $P$ 。沿 $P$ 两侧的单位网格边作边界轨迹，并在四条边交于同一格点时，按“能够共点移动的非 $P$ 格子位于同一侧”唯一配对。由此得到的边界轨迹将 $A,B$ 分开；任何连接 $A,B$ 的八联通格链都必须和 $P$ 共用一个格子。

因而障碍墙存在时，任何避开 $B_k$ 的四联通路径都会和它相交，矛盾。反过来，删除 $B_k$ 后令 $R$ 为从 $[1,1]$ 可达的格子集合。若终点不可达，取 $R$ 与其补集的边界轨迹。每条内部边界的非 $R$ 一侧都属于 $B_k$ ，否则这个格子也应可达。沿外框两段分别从起点走到终点，边界端点的奇偶性说明存在一条轨迹连接 $A,B$ ；取其非 $R$ 一侧格子，便得到一个八联通的 $B_k$ 障碍墙。

【实现】

从四条边界出发，对数值相同的格子进行八联通 DFS，并记录连通块从哪一条边界开始。若该连通块到达另一组边界，就标记该数值不能绕开。每个格子只进入一次 DFS，最后从 $0$ 开始找第一个未标记的数值。

【复杂度分析】

时间复杂度、空间复杂度均为 $\mathcal{O}(nm)$ 。

【参考代码】

1#include <queue>2#include <cstdio>3#include <cstring>4#include <algorithm>5using namespace std;6int T;7int n,m,Line[2010][2010];8bool Tag[4010];9bool Visit[2010][2010];10inline int read()11{12    int x=0,f=1;13    char ch=getchar();14    while(ch<'0'||ch>'9')15    {16        if(ch=='-')17            f=-1;18        ch=getchar();19    }20    while(ch>='0' && ch<='9')21        x=x*10+ch-'0',ch=getchar();22    return x*f;23}24void DFS(int i,int j,int W) {25    if (Visit[i][j]) return;26    Visit[i][j]=1;27    if (i==1&&W!=3&&W!=2) Tag[Line[i][j]]=1;28    if (i==n&&W!=4&&W!=1) Tag[Line[i][j]]=1;29    if (j==1&&W!=1&&W!=4) Tag[Line[i][j]]=1;30    if (j==m&&W!=2&&W!=3) Tag[Line[i][j]]=1;31    if (Line[i+1][j]==Line[i][j]&&i+1<=n) DFS(i+1,j,W);32    if (Line[i-1][j]==Line[i][j]&&i-1>=1) DFS(i-1,j,W);33    if (Line[i][j+1]==Line[i][j]&&j+1<=m) DFS(i,j+1,W);34    if (Line[i][j-1]==Line[i][j]&&j-1>=1) DFS(i,j-1,W);35 36    if (Line[i+1][j+1]==Line[i][j]&&i+1<=n&&j+1<=m) DFS(i+1,j+1,W);37    if (Line[i-1][j+1]==Line[i][j]&&i-1>=1&&j+1<=m) DFS(i-1,j+1,W);38    if (Line[i+1][j-1]==Line[i][j]&&i+1<=n&&j-1>=1) DFS(i+1,j-1,W);39    if (Line[i-1][j-1]==Line[i][j]&&i-1>=1&&j-1>=1) DFS(i-1,j-1,W);40    return;41}42void Solve() {43    memset(Tag,0,sizeof(Tag));44    scanf("%d%d",&n,&m);45    for (int i=1;i<=n;i++) {46        for (int j=1;j<=m;j++) {47            Line[i][j]=read();48            Visit[i][j]=0;49        }50    }51    for (int i=1;i<=n;i++) {52        if (Line[i][1]<=n+m) DFS(i,1,1);53        if (Line[i][m]<=n+m) DFS(i,m,2);54    }55    for (int i=1;i<=m;i++) {56        if (Line[1][i]<=n+m) DFS(1,i,3);57        if (Line[n][i]<=n+m) DFS(n,i,4);58    }59    for (int i=0;i<=n+m;i++) {60        if (!Tag[i]){ printf("%d\n",i); return;}61    }62}63int main() {64    scanf("%d",&T);65    while (T-->0) Solve();66    return 0;67}