1050 - Manhattan Wiring

Time Limit : 5 Second

Memory Limit : 128 MB

Submission: 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
© 2015 HUST ACMICPC TEAM. All Right Reserved.