2026 杭电春季联赛 4——1001-布布吃地瓜

题目大意

题目描述
给定一个 $n \times m$ 的网格，每个格子 $(i, j)$ 中包含一个非负整数 $a_{i, j}$。
你需要从左上角 $(1, 1)$ 出发，经过上下左右四连通的合法移动，最终到达右下角 $(n, m)$，移动过程中不能离开网格。
令 $S$ 表示路径上经过的所有格子中的整数构成的集合，$\text{mex}(S)$ 表示集合 $S$ 中未出现的最小非负整数。
求出所有从 $(1, 1)$ 到 $(n, m)$ 的路径中，可能得到的最小的 $\text{mex}(S)$ 值。

输入格式
第一行包含一个整数 $T$（$1 \le T \le 1000$），表示测试数据组数。
对于每组数据：
第一行包含两个整数 $n$ 和 $m$（$\sum n \le 2000$，$\sum m \le 2000$）。
接下来 $n$ 行，每行 $m$ 个整数，表示网格中的数字 $a_{i, j}$（$0 \le a_{i, j} \le 10^9$）。

输出格式
对于每组测试数据，输出可能得到的最小的 $\text{mex}(S)$。

样例输入

1
3 3
0 0 0
0 0 0
0 0 0

样例输出

1

样例解释
在此样例中，给定了 $3 \times 3$ 的网格，且所有格子内的数字均为 0。无论布布选择哪一条从 $(1, 1)$ 走到 $(3, 3)$ 的合法路径，路径上经过的数字集合 $S$ 必然只包含元素 0，即 $S = \{0\}$。在集合 $\{0\}$ 中，未出现的最小非负整数是 1，因此可能得到的最小的 $\text{mex}(S)$ 为 1。

思路讲解

我们的思路（AI 总结的）这个 latex 代码

\documentclass{article}

\usepackage{graphicx} % Required for inserting images
\usepackage{amsmath} % bmatrix、cases、aligned 等数学环境
\usepackage{amssymb} % 数学符号宏包，支持 \mathbb 等
\usepackage{xeCJK} % 核心：添加这个宏包以支持中文
\usepackage{multicol} % 引入分栏宏包
\usepackage{tocloft} % 支持目录引导点
\usepackage{xcolor}   % 用于设置颜色；须先于 minted 以便 bgcolor 等生效
\usepackage[cachedir=_minted-main]{minted} % Pygments 高亮，需 -shell-escape + pygmentize
\usepackage[a4paper, left=2cm, right=2cm, top=2.5cm, bottom=2.5cm]{geometry}
\usepackage{tikz}

% 与原先 listings 外观大致对齐；
\setminted{
	% 允许长行换行
	breaklines=true,
	% 允许在任意位置换行，防止长 URL 戳出去
	breakanywhere=true,
	fontsize=\small,
	frame=single,
	bgcolor=gray!5,
	tabsize=2,
}

% --- 目录样式修改 ---
\renewcommand{\cftsecleader}{\cftdotfill{\cftdotsep}} % 让 section 也有点点
% ------------------

\usepackage[colorlinks=true, linkcolor=black, anchorcolor=black, citecolor=black, filecolor=black, menucolor=black, runcolor=black, urlcolor=blue]{hyperref} % 添加超链接和PDF书签支持

\definecolor{arcA}{RGB}{220,80,60}    % 红色 — 弧 A
\definecolor{arcB}{RGB}{50,120,200}   % 蓝色 — 弧 B
\definecolor{barrier}{RGB}{255,160,0} % 橙色 — 屏障
\definecolor{pathc}{RGB}{0,160,80}    % 绿色 — 路径

\title{1001 布布吃地瓜 题解}
\author{Gospel\_rock}
\date{}

\begin{document}
\maketitle

\section{题意}

给定一个 $n \times m$ 的网格，格子 $(i,j)$ 上写着整数 $a_{i,j}$。
从 $(1,1)$ 出发，经四连通移动到 $(n,m)$，不能离开网格。
令 $S$ 为路径上所有格子中整数构成的集合，求所有合法路径中 $\text{mex}(S)$ 的最小值。

\section{核心观察：路径—屏障对偶}

问题等价于：对每个非负整数 $k$，判断是否\textbf{每条} $(1,1) \to (n,m)$ 的四连通路径都必须经过至少一个值为 $k$ 的格子。如果是，则 $k$ 一定在集合 $S$ 中（称 $k$ 为\textbf{不可避免的}）；否则存在某条路径绕开所有值为 $k$ 的格子（称 $k$ 为\textbf{可避免的}）。答案即为最小的可避免值。

判断 $k$ 是否不可避免，依赖于网格上\textbf{路径与屏障的对偶性}——这是离散 Jordan 曲线定理在网格图上的直接推论。

\subsection{边界弧的划分}

将网格的边界沿周长分为两段弧，以 $(1,1)$ 和 $(n,m)$ 为分界点（如图~\ref{fig:arc}）：
\begin{itemize}
	\item \textbf{弧 $\boldsymbol{A}$}（红色）：从 $(1,1)$ 沿顶边向右到 $(1,m)$，再沿右边向下到 $(n,m)$。
	\item \textbf{弧 $\boldsymbol{B}$}（蓝色）：从 $(1,1)$ 沿左边向下到 $(n,1)$，再沿底边向右到 $(n,m)$。
\end{itemize}

\begin{figure}[htbp]
\centering
\begin{tikzpicture}[scale=0.9]
	% 画网格
	\foreach \i in {0,...,5} {
		\draw[gray!40] (\i,0) -- (\i,4);
	}
	\foreach \j in {0,...,4} {
		\draw[gray!40] (0,\j) -- (5,\j);
	}
	% 弧 A：顶边 + 右边
	\draw[arcA, line width=3pt] (0,4) -- (5,4);
	\draw[arcA, line width=3pt] (5,4) -- (5,0);
	% 弧 B：左边 + 底边
	\draw[arcB, line width=3pt] (0,4) -- (0,0);
	\draw[arcB, line width=3pt] (0,0) -- (5,0);
	% 标注起止点
	\fill[black] (0,4) circle (4pt) node[above left] {$(1,1)$};
	\fill[black] (5,0) circle (4pt) node[below right] {$(n,m)$};
	% 图例
	\draw[arcA, line width=2.5pt] (6.2,3.8) -- (7.2,3.8) node[right, black] {弧 $A$};
	\draw[arcB, line width=2.5pt] (6.2,3.0) -- (7.2,3.0) node[right, black] {弧 $B$};
\end{tikzpicture}
\caption{边界弧的划分。$(1,1)$ 和 $(n,m)$ 将网格边界分成红、蓝两段弧。}
\label{fig:arc}
\end{figure}

\subsection{对偶定理}

\begin{quote}
\textbf{定理（网格路径—屏障对偶）}\;
在 $n \times m$ 的网格中，不存在从 $(1,1)$ 到 $(n,m)$ 的四连通路径能完全避开值为 $k$ 的格子，当且仅当值为 $k$ 的格子中存在一个\textbf{八连通}连通分量，同时触及弧 $A$ 和弧 $B$。
\end{quote}

直觉上很好理解：任何一条从 $(1,1)$ 到 $(n,m)$ 的四连通路径，都会将网格"切割"为两部分——一部分靠近弧 $A$，另一部分靠近弧 $B$。若一群同值格子八连通地从弧 $A$ 连到弧 $B$，则这群格子构成了一道"墙"，任何四连通路径都无法从"墙"的缝隙中穿过（四连通无法斜穿八连通的间隙），因此必须踩到墙上。

图~\ref{fig:barrier} 展示了一个具体例子。

\begin{figure}[htbp]
\centering
\begin{tikzpicture}[scale=1.0]
	% 画网格底色
	\foreach \i in {0,...,5} {
		\foreach \j in {0,...,4} {
			\fill[gray!8] (\i,\j) rectangle ++(1,1);
		}
	}
	% 画网格线
	\foreach \i in {0,...,6} {
		\draw[gray!40] (\i,0) -- (\i,5);
	}
	\foreach \j in {0,...,5} {
		\draw[gray!40] (0,\j) -- (6,\j);
	}

	% 屏障格子（值为 k 的八连通链：从弧 A 到弧 B）
	\foreach \x/\y in {4/4, 3/3, 3/2, 2/1, 1/0} {
		\fill[barrier!60] (\x,\y) rectangle ++(1,1);
		\node[font=\bfseries] at (\x+0.5,\y+0.5) {$k$};
	}

	% 弧 A
	\draw[arcA, line width=2.5pt] (0,5) -- (6,5);
	\draw[arcA, line width=2.5pt] (6,5) -- (6,0);
	% 弧 B
	\draw[arcB, line width=2.5pt] (0,5) -- (0,0);
	\draw[arcB, line width=2.5pt] (0,0) -- (6,0);

	% 路径（四连通，必须穿过屏障）
	\draw[pathc, line width=2pt, -stealth]
		(0.5,4.5) -- (0.5,3.5) -- (0.5,2.5) -- (0.5,1.5)
		-- (1.5,1.5) -- (2.5,1.5) -- (2.5,2.5)
		-- (3.5,2.5) % 踩到屏障
		-- (3.5,1.5) -- (3.5,0.5)
		-- (4.5,0.5) -- (5.5,0.5);

	% 标注起止点
	\fill[black] (0.5,4.5) circle (3.5pt);
	\node[above left, font=\small] at (0.5,4.5) {$(1,1)$};
	\fill[black] (5.5,0.5) circle (3.5pt);
	\node[below right, font=\small] at (5.5,0.5) {$(n,m)$};

	% 标注踩到屏障的位置
	\draw[-stealth, thick, red!70!black] (4.8,3.2) -- (3.8,2.7);
	\node[right, font=\small, red!70!black] at (4.8,3.2) {必经！};

	% 图例
	\fill[barrier!60] (7,4) rectangle ++(0.6,0.6);
	\node[right, font=\small] at (7.8,4.3) {值为 $k$ 的屏障};
	\draw[pathc, line width=2pt] (7,3.3) -- (7.6,3.3);
	\node[right, font=\small] at (7.8,3.3) {四连通路径};
\end{tikzpicture}
\caption{值为 $k$ 的格子（橙色）八连通地从弧 $A$（顶边）连到弧 $B$（底边），形成屏障。任何四连通路径（绿色）都必须踩到至少一个橙色格子。}
\label{fig:barrier}
\end{figure}

\section{算法流程}

根据对偶定理，算法只需逐一判断每个值是否构成屏障即可。

\begin{enumerate}
	\item 将候选集合 $C \leftarrow \{0, 1, 2, \ldots, n + m\}$。
	\item 枚举弧 $A$ 上的每个格子 $(i,j)$（即第 $1$ 行的所有格子与第 $m$ 列的所有格子），
		  对尚未访问的格子发起\textbf{八连通 DFS}，仅扩展值相同的邻居。
	\item 若 DFS 过程中到达了弧 $B$ 上的某个格子（即第 $1$ 列或第 $n$ 行），
		  说明当前值 $v$ 构成屏障，从 $C$ 中删除 $v$。
	\item 所有弧 $A$ 上的格子处理完毕后，$C$ 中的最小元素即为答案。
\end{enumerate}

为什么只需从弧 $A$ 出发搜索？因为屏障必须\textbf{同时}触及弧 $A$ 与弧 $B$，从弧 $A$ 出发的同值连通分量若能到达弧 $B$，就恰好满足此条件。

\subsection{复杂度分析}

每个格子至多被访问一次（DFS 中标记 \texttt{vis}），因此总时间复杂度为 $O(nm)$，空间复杂度为 $O(nm)$。

\section{AC 代码}

\inputminted{cpp}{../src/1001_2.cpp}

\end{document}

PDF

找出所有的这个值为 k 的屏障。

这个代码就是看哪些值是避无可避的。

for (int y = 1; y <= M; ++y) {
    if (vis[1][y]) {
        continue;
    }
    vis[1][y] = 1;
    if (dfs(1, y,1,y)) {
        st.erase(maze[1][y]);
    }
}
for (int x = 1; x <= N; ++x) {
    if (vis[x][M]) {
        continue;
    }
    vis[x][M] = 1;
    if (dfs(x, M,x,M)) {
        st.erase(maze[x][M]);
    }
}

AC代码

源代码

心路历程（WA，TLE，MLE……）