1050 - Manhattan Wiring

Time Limit: 5s Memory Limit: 128MB

Submissions: 30 Solved: 17
Description
There is a rectangle area containing n*m cells. Two cells are maked whith '2',and another two with '3'. Some cells are occupied by obstactes. You should connect the two '2's and also the two '3's with no-intersecting lines. lines can run only vertically or horizontally conecting centers of cells without obstacles; Lines cann't run on a cell with an obstacle.Only one line can run on a cell at most once.Hence a line cann,t intersert with the other line,or wirth itself.Under these constraints,the total length of the two lines should be minimized.The length of a line defined as the the number of cellborders it passes.In partcular ,a line connecting cells sharing their border has length 1. Figure (a) above shows a example setting. Figure (b) shows lines satisfying the constraints above with minimum total lenth 18.
Input
The input consists of multiple datasets,each in the follwing format. n m row1 .... rown n is the number of rows.(2<=n<=9). m is the number of columns.(2<=m<=9). Each rowi,is sequence of m digits separated by a space.The digtals mean the following: 0:Empty 1:Cooupied by an obstacle 2:Marked with '2' 3:Marked with '3' The end of the input is indicated with a line containing two zeros separated by a space.
Output
For each dataset, one line cotains the minimum total length of the two lines should be ouput; If there is no pair of lines satisfying the requirement, answer '0' instead. No other characters should be contained in the output.
Sample Input
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
0 0
Sample Output
18
2
Hint
Source