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