SP3926 MMAHWIRE - Manhattan Wire

在一个由 $n \times m$ 格子组成的矩形区域内，有两个格子标记为“2”，另有两个格子标记为“3”。部分格子被障碍物占据。你的任务是用两条不相交的路径分别连接两个“2”和两个“3”。路径只能垂直或水平穿过没有障碍物的格子。 路径不能经过障碍物所在的格子，每个格子最多只能被一条路径使用一次。因此，一条路径不能与另一条路径交叉，也不能自相交。在这些限制条件下，你需要让两条路径的总长度尽可能短。路径的长度定义为它经过的格子边界的数量。具体而言，连接相邻格子的路径长度为 1。 图 1(a) 显示了一个示例配置。图 1(b) 显示了在这些约束条件下，总长度最小（18）的两条路径。

输入由多个数据集组成，每个数据集的格式如下： ``` n m row1 … rown ``` 其中，$n$ 表示行数，满足 $2 \le n \le 9$；$m$ 表示列数，满足 $2 \le m \le 9$。每行 `rowi` 是由 $m$ 个数字组成的序列，数字之间用空格分隔。这些数字表示： - 0：空格 - 1：障碍物 - 2：标记为“2” - 3：标记为“3” 输入以一行“0 0”结束。 **样例输入** ``` 5 5 0 0 0 0 0 0 0 0 3 0 2 0 2 0 0 1 0 1 1 1 0 0 0 0 3 2 3 2 2 0 0 3 3 6 5 2 0 0 0 0 0 3 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 2 3 0 0 0 ```

对于每个数据集，输出一行，其内容为两条路径的最小总长度。如果找不到满足条件的路径对，则输出 `0`。 **样例输出** ``` 18 2 17 ``` **本翻译由 AI 自动生成**