MMAHWIRE  Manhattan Wire
English  Vietnamese 
There is a rectangular area containing n × m cells. Two cells are marked with “2”, and another two with “3”. Some cells are occupied by obstacles. You should connect the two “2”s and also the two “3”s with nonintersecting lines. Lines can run only vertically or horizontally connecting centers of cells without obstacles. Lines cannot run on a cell with an obstacle. Only one line can run on a cell at most once. Hence, a line cannot intersect with the other line, nor with itself. Under these constraints, the total length of the two lines should be minimized. The length of a line is defined as the number of cell borders it passes. In particular, a line connecting cells sharing their border has length 1. Fig. 1(a) shows an example setting. Fig. 1(b) shows two lines satisfying the constraints above with minimum total length 18. Figure 1: An example of setting and its solution
Input
The input consists of multiple datasets, each in the following format. n m row1 … rown n is the number of rows which satisfies 2 ≤ n ≤ 9. m is the number of columns which satisfies 2 ≤ m ≤ 9. Each rowi is a sequence of m digits separated by a space. The digits mean the following. 0: Empty 1: Occupied 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. 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 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
Output
For each dataset, one line containing the minimum total length of the two lines should be output. If there is no pair of lines satisfying the requirement, answer “0” instead. Sample Output 18 2 17
hide comments
Patrick Klitzke:
20120422 18:16:19
I agree, my solution is quite fast, on most testcases it is a fraction of a second, but I get TLE. It is really not fun optimizing all day long... 

Kliment Serafimov:
20120421 14:59:32
this is the worst test case I found:


Buda IM (retired):
20120408 21:39:15
@Marko Stankovic


Marko Stankovic:
20120407 16:19:55
Why is TL 1s4s. Shouldn't it be a single value?


[Trichromatic] XilinX:
20091203 01:01:06
Time limit too strict! 
Added by:  ~!(*(@*!@^& 
Date:  20090222 
Time limit:  0.100s0.435s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ERL JSRHINO NODEJS PERL6 VB.NET 
Resource:  Yokohama 2006 