解题思路

网格没有障碍，两点间最短路就是曼哈顿距离。必访点是所有非 $0$ 格子，起点和终点都是中心，因此是带固定起点的 TSP。

把中心记为点 $0$ ，再把中心以外的非 $0$ 格子依次编号。格子可以重复路过， $0$ 格子只作为通道。
若只有中心这一个点，答案为 $0$ 。
用状压 DP： $dp[\textit{mask}][i]$ 表示已经访问过集合 $\textit{mask}$ 、当前停在 $i$ 的最少步数。初始 $dp[1][0]=0$ 。
转移：从 $i$ 走到尚未访问的 $j$ ，更新 $dp[\textit{mask}\cup\{j\}][j]$ 。
最后对全集上每个终点 $i$ ，加上回到中心的距离，取最小值。

题目内容

给定 $n$ 行 $m$ 列的格子，从中心出发，访问所有非 $0$ 格子至少一次后再回到中心，求最少步数。每次可向上下左右走一格，计为一步。中心为第 $\lfloor n/2\rfloor$ 行、第 $\lfloor m/2\rfloor$ 列（行列下标从 $0$ 开始）。

第一行两个奇数 $n$ 和 $m$ 。

接下来 $n$ 行，每行 $m$ 个整数，表示格子上的值。

输出一个整数，表示最少步数。

输入：

输出：

说明：中心为 $(1,1)$ 。一条最优路线为中心 $\to(0,0)\to(2,0)\to$ 中心，曼哈顿距离分别为 $2$ 、 $2$ 、 $2$ ，总步数 $6$ 。

选择提交后点击「开始AI分析」