题目描述

Poj 3133

给你一个棋盘，棋盘中有一些格子会设置障碍，除此之外，我们还会放置两个“ $2$ ”和两个“ $3$ ”，现在要求你把两个“ $2$ ”和两个“ $3$ ”分别用两条路径连起来，这两条路径只能经过无障碍格子，每个格子只能被经过一次，也可以不经过，并且这两条路径不能相交。现在让你求一种方案，使这两条路径经过的格子总数最少，输出这个总数 $-2$ 后的结果。

如图，一个 $5*5$ 的棋盘，$(4,1)$，$(4,3)$，$(4,4)$ 和 $(4,5)$ 是障碍格子，将图中两个“ $2$ ”和两个“ $3$ ”连起来，一共经过了 $20$ 个格子，所以输出 $18$。

输入格式

多组数据，每组数据的第一行有两个整数 $n$ 和 $m$，表示给你一个 $n * m$ $(1 < n,m \le 10)$ 的棋盘，接下来描述这个棋盘，“ $1$ ”表示该格子有障碍，“ $0$ ”则表示该格子无障碍。当 $n=m=0$ 时，输入结束。

输出格式

对于每组数据，输出 经过格子总数最少的数量 $-2$ 后的结果，如果无法按要求将两个“ $2$ ”和两个“ $3$ ”连起来，则输出“ $0$ ”。

输入输出样例

输入 #1

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
5 9
0 0 0 0 0 0 0 0 0
0 0 0 0 3 0 0 0 0
0 2 0 0 0 0 0 2 0
0 0 0 0 3 0 0 0 0
0 0 0 0 0 0 0 0 0
9 9
3 0 0 0 0 0 0 0 2
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
2 0 0 0 0 0 0 0 3
9 9
0 0 0 1 0 0 0 0 0
0 2 0 1 0 0 0 0 3
0 0 0 1 0 0 0 0 2
0 0 0 1 0 0 0 0 3
0 0 0 1 1 1 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
9 9
0 0 0 0 0 0 0 0 0
0 3 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 2 3 2
0 0

输出 #1

18
2
17
12
0
52
43