시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 0 0 0 0.000%

문제

n * m 칸으로 이루어진 직사각형 영역이 있다. 이 중, 두 칸은 "2"로 표시되어 있고, 다른 두 칸은 "3"으로 표시되어 있다. 어떤 칸에는 장애물이 있다. 이 때, 두 "2"와 두 "3"을 교차하지 않는 선분으로 이으려고 한다. 선은 장애물이 아닌 칸의 중심을 가로 또는 세로로 연결할 수 있다.

한 칸에는 최대 1개의 선만 있을 수 있고, 선이 서로 교차할수는 없다. 이 때, 두 선의 길이의 합이 최소가 되는 것을 찾으려고 한다. 선의 길이는 선이 통과하는 칸의 경계의 개수이다. 즉, 경계를 공유하는 두 칸을 이은 선의 길이는 1이다.

아래 그림 (a)는 영역의 예시이고, (b)는 위의 조건을 만족하게 선을 그린 것이고, 길이는 18이다.

입력

입력은 여러 개의 데이터 세트로 이루어져 있다. 첫째 줄에는 데이터 세트의 개수 T가 주어진다. 다음 줄부터는 각각의 데이터 세트의 정보가 주어지며, 다음과 같이 구성되어져 있다.

첫째 줄에는 행의 개수 n과 열의 개수 m이 주어진다. (2 ≤ n ≤ 9, 2 ≤ m ≤ 9) 다음 줄부터 n개의 줄에는 1행의 정보부터 n행의 정보가 한 줄에 하나식 주어지며, m개의 숫자가 공백으로 구분되어 있다. 숫자의 의미는 다음과 같다.

0: 빈 칸

1: 장애물

2: "2"로 표시된 곳

3: "3"으로 표시된 곳

출력

각각의 데이터 세트에 대해서, 문제의 조건을 만족하는 두 선의 길이의 최소값을 출력한다. 만약, 조건을 만족하는 선을 그릴 수 없다면 "0"을 출력한다.

예제 입력 1

7
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

예제 출력 1

18
2
17
12
0
52
43

힌트

W3sicHJvYmxlbV9pZCI6IjM5MDkiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWI5ZThcdWQ1NThcdWQwYzQgXHViYzMwXHVjMTIwIiwiZGVzY3JpcHRpb24iOiI8cD5cclxuXHRuICogbSBcdWNlNzhcdWM3M2NcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjOWM0IFx1YzljMVx1YzBhY1x1YWMwMVx1ZDYxNSBcdWM2MDFcdWM1ZWRcdWM3NzQgXHVjNzg4XHViMmU0LiBcdWM3NzQgXHVjOTExLCBcdWI0NTAgXHVjZTc4XHVjNzQwICZxdW90OzImcXVvdDtcdWI4NWMgXHVkNDVjXHVjMmRjXHViNDE4XHVjNWI0IFx1Yzc4OFx1YWNlMCwgXHViMmU0XHViOTc4IFx1YjQ1MCBcdWNlNzhcdWM3NDAgJnF1b3Q7MyZxdW90O1x1YzczY1x1Yjg1YyBcdWQ0NWNcdWMyZGNcdWI0MThcdWM1YjQgXHVjNzg4XHViMmU0LiBcdWM1YjRcdWI1YTQgXHVjZTc4XHVjNWQwXHViMjk0IFx1YzdhNVx1YzU2MFx1YmIzY1x1Yzc3NCBcdWM3ODhcdWIyZTQuIFx1Yzc3NCBcdWI1NGMsIFx1YjQ1MCAmcXVvdDsyJnF1b3Q7XHVjNjQwIFx1YjQ1MCAmcXVvdDszJnF1b3Q7XHVjNzQ0IFx1YWQ1MFx1Y2MyOFx1ZDU1OFx1YzljMCBcdWM1NGFcdWIyOTQgXHVjMTIwXHViZDg0XHVjNzNjXHViODVjIFx1Yzc3NFx1YzczY1x1YjgyNFx1YWNlMCBcdWQ1NWNcdWIyZTQuIFx1YzEyMFx1Yzc0MCBcdWM3YTVcdWM1NjBcdWJiM2NcdWM3NzQgXHVjNTQ0XHViMmNjIFx1Y2U3OFx1Yzc1OCBcdWM5MTFcdWMyZWNcdWM3NDQgXHVhYzAwXHViODVjIFx1YjYxMFx1YjI5NCBcdWMxMzhcdWI4NWNcdWI4NWMgXHVjNWYwXHVhY2IwXHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlxyXG5cdFx1ZDU1YyBcdWNlNzhcdWM1ZDBcdWIyOTQgXHVjZDVjXHViMzAwIDFcdWFjMWNcdWM3NTggXHVjMTIwXHViOWNjIFx1Yzc4OFx1Yzc0NCBcdWMyMTggXHVjNzg4XHVhY2UwLCBcdWMxMjBcdWM3NzQgXHVjMTFjXHViODVjIFx1YWQ1MFx1Y2MyOFx1ZDU2MFx1YzIxOFx1YjI5NCBcdWM1YzZcdWIyZTQuIFx1Yzc3NCBcdWI1NGMsIFx1YjQ1MCBcdWMxMjBcdWM3NTggXHVhZTM4XHVjNzc0XHVjNzU4IFx1ZDU2OVx1Yzc3NCBcdWNkNWNcdWMxOGNcdWFjMDAgXHViNDE4XHViMjk0IFx1YWM4M1x1Yzc0NCBcdWNjM2VcdWM3M2NcdWI4MjRcdWFjZTAgXHVkNTVjXHViMmU0LiBcdWMxMjBcdWM3NTggXHVhZTM4XHVjNzc0XHViMjk0IFx1YzEyMFx1Yzc3NCBcdWQxYjVcdWFjZmNcdWQ1NThcdWIyOTQgXHVjZTc4XHVjNzU4IFx1YWNiZFx1YWNjNFx1Yzc1OCBcdWFjMWNcdWMyMThcdWM3NzRcdWIyZTQuIFx1Yzk4OSwgXHVhY2JkXHVhY2M0XHViOTdjIFx1YWNmNVx1YzcyMFx1ZDU1OFx1YjI5NCBcdWI0NTAgXHVjZTc4XHVjNzQ0IFx1Yzc3NFx1Yzc0MCBcdWMxMjBcdWM3NTggXHVhZTM4XHVjNzc0XHViMjk0IDFcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlxyXG5cdFx1YzU0NFx1Yjc5OCBcdWFkZjhcdWI5YmMgKGEpXHViMjk0IFx1YzYwMVx1YzVlZFx1Yzc1OCBcdWM2MDhcdWMyZGNcdWM3NzRcdWFjZTAsIChiKVx1YjI5NCBcdWM3MDRcdWM3NTggXHVjODcwXHVhYzc0XHVjNzQ0IFx1YjljY1x1Yzg3MVx1ZDU1OFx1YWM4YyBcdWMxMjBcdWM3NDQgXHVhZGY4XHViOWIwIFx1YWM4M1x1Yzc3NFx1YWNlMCwgXHVhZTM4XHVjNzc0XHViMjk0IDE4XHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cclxuXHQ8aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL21hbi5wbmdcIiBzdHlsZT1cIndpZHRoOiAzMTBweDsgaGVpZ2h0OiAxNjlweDtcIiBcLz48XC9wPlxyXG4iLCJpbnB1dCI6IlxyXG48cD5cclxuXHRcdWM3ODVcdWI4MjVcdWM3NDAgXHVjNWVjXHViN2VjIFx1YWMxY1x1Yzc1OCBcdWIzNzBcdWM3NzRcdWQxMzAgXHVjMTM4XHVkMmI4XHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWIyZTQuIFx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHViMzcwXHVjNzc0XHVkMTMwIFx1YzEzOFx1ZDJiOFx1Yzc1OCBcdWFjMWNcdWMyMTggVFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YjJlNFx1Yzc0YyBcdWM5MDRcdWJkODBcdWQxMzBcdWIyOTQgXHVhYzAxXHVhYzAxXHVjNzU4IFx1YjM3MFx1Yzc3NFx1ZDEzMCBcdWMxMzhcdWQyYjhcdWM3NTggXHVjODE1XHViY2Y0XHVhYzAwIFx1YzhmY1x1YzViNFx1YzljMFx1YmE3MCwgXHViMmU0XHVjNzRjXHVhY2ZjIFx1YWMxOVx1Yzc3NCBcdWFkNmNcdWMxMzFcdWI0MThcdWM1YjRcdWM4MzggXHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cclxuXHRcdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IFx1ZDU4OVx1Yzc1OCBcdWFjMWNcdWMyMTggblx1YWNmYyBcdWM1ZjRcdWM3NTggXHVhYzFjXHVjMjE4IG1cdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoMiAmbGU7IG4gJmxlOyA5LCAyICZsZTsgbSAmbGU7IDkpIFx1YjJlNFx1Yzc0YyBcdWM5MDRcdWJkODBcdWQxMzAgblx1YWMxY1x1Yzc1OCBcdWM5MDRcdWM1ZDBcdWIyOTQgMVx1ZDU4OVx1Yzc1OCBcdWM4MTVcdWJjZjRcdWJkODBcdWQxMzAgblx1ZDU4OVx1Yzc1OCBcdWM4MTVcdWJjZjRcdWFjMDAgXHVkNTVjIFx1YzkwNFx1YzVkMCBcdWQ1NThcdWIwOThcdWMyZGQgXHVjOGZjXHVjNWI0XHVjOWMwXHViYTcwLCBtXHVhYzFjXHVjNzU4IFx1YzIyYlx1Yzc5MFx1YWMwMCBcdWFjZjVcdWJjMzFcdWM3M2NcdWI4NWMgXHVhZDZjXHViZDg0XHViNDE4XHVjNWI0IFx1Yzc4OFx1YjJlNC4gXHVjMjJiXHVjNzkwXHVjNzU4IFx1Yzc1OFx1YmJmOFx1YjI5NCBcdWIyZTRcdWM3NGNcdWFjZmMgXHVhYzE5XHViMmU0LjxcL3A+XHJcblxyXG48cD5cclxuXHQwOiBcdWJlNDggXHVjZTc4PFwvcD5cclxuPHA+XHJcblx0MTogXHVjN2E1XHVjNTYwXHViYjNjPFwvcD5cclxuPHA+XHJcblx0MjogJnF1b3Q7MiZxdW90O1x1Yjg1YyBcdWQ0NWNcdWMyZGNcdWI0MWMgXHVhY2YzPFwvcD5cclxuPHA+XHJcblx0MzogJnF1b3Q7MyZxdW90O1x1YzczY1x1Yjg1YyBcdWQ0NWNcdWMyZGNcdWI0MWMgXHVhY2YzPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHJcblx0XHVhYzAxXHVhYzAxXHVjNzU4IFx1YjM3MFx1Yzc3NFx1ZDEzMCBcdWMxMzhcdWQyYjhcdWM1ZDAgXHViMzAwXHVkNTc0XHVjMTFjLCBcdWJiMzhcdWM4MWNcdWM3NTggXHVjODcwXHVhYzc0XHVjNzQ0IFx1YjljY1x1Yzg3MVx1ZDU1OFx1YjI5NCBcdWI0NTAgXHVjMTIwXHVjNzU4IFx1YWUzOFx1Yzc3NFx1Yzc1OCBcdWNkNWNcdWMxOGNcdWFjMTJcdWM3NDQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LiBcdWI5Y2NcdWM1N2QsIFx1Yzg3MFx1YWM3NFx1Yzc0NCBcdWI5Y2NcdWM4NzFcdWQ1NThcdWIyOTQgXHVjMTIwXHVjNzQ0IFx1YWRmOFx1YjliNCBcdWMyMTggXHVjNWM2XHViMmU0XHViYTc0ICZxdW90OzAmcXVvdDtcdWM3NDQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjM5MDkiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJNYW5oYXR0YW4gV2lyaW5nIiwiZGVzY3JpcHRpb24iOiI8cD5UaGVyZSBpcyBhIHJlY3Rhbmd1bGFyIGFyZWEgY29udGFpbmluZyBuIHggbSBjZWxscy4gVHdvIGNlbGxzIGFyZSBtYXJrZWQgd2l0aCAmcXVvdDsyJnF1b3Q7LCBhbmQgYW5vdGhlciB0d28gd2l0aCAmcXVvdDszJnF1b3Q7LiBTb21lIGNlbGxzIGFyZSBvY2N1cGllZCBieSBvYnN0YWNsZXMuIFlvdSBzaG91bGQgY29ubmVjdCB0aGUgdHdvICZxdW90OzImcXVvdDtzIGFuZCBhbHNvIHRoZSB0d28gJnF1b3Q7MyZxdW90O3Mgd2l0aCBub24taW50ZXJzZWN0aW5nIGxpbmVzLiBMaW5lcyBjYW4gcnVuIG9ubHkgdmVydGljYWxseSBvciBob3Jpem9udGFsbHkgY29ubmVjdGluZyBjZW50ZXJzIG9mIGNlbGxzIHdpdGhvdXQgb2JzdGFjbGVzLjxcL3A+XHJcblxyXG48cD5MaW5lcyBjYW5ub3QgcnVuIG9uIGEgY2VsbCB3aXRoIGFuIG9ic3RhY2xlLiBPbmx5IG9uZSBsaW5lIGNhbiBydW4gb24gYSBjZWxsIGF0IG1vc3Qgb25jZS4gSGVuY2UsIGEgbGluZSBjYW5ub3QgaW50ZXJzZWN0IHdpdGggdGhlIG90aGVyIGxpbmUsIG5vciB3aXRoIGl0c2VsZi4gVW5kZXIgdGhlc2UgY29uc3RyYWludHMsIHRoZSB0b3RhbCBsZW5ndGggb2YgdGhlIHR3byBsaW5lcyBzaG91bGQgYmUgbWluaW1pemVkLiBUaGUgbGVuZ3RoIG9mIGEgbGluZSBpcyBkZWZpbmVkIGFzIHRoZSBudW1iZXIgb2YgY2VsbCBib3JkZXJzIGl0IHBhc3Nlcy4gSW4gcGFydGljdWxhciwgYSBsaW5lIGNvbm5lY3RpbmcgY2VsbHMgc2hhcmluZyB0aGVpciBib3JkZXIgaGFzIGxlbmd0aCAxLjxcL3A+XHJcblxyXG48cD5GaWcuIDYoYSkgc2hvd3MgYW4gZXhhbXBsZSBzZXR0aW5nLiBGaWcuIDYoYikgc2hvd3MgdHdvIGxpbmVzIHNhdGlzZnlpbmcgdGhlIGNvbnN0cmFpbnRzIGFib3ZlIHdpdGggbWluaW11bSB0b3RhbCBsZW5ndGggMTguPFwvcD5cclxuXHJcbjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wvbWFuLnBuZ1wiIHN0eWxlPVwiaGVpZ2h0OjE2OXB4OyB3aWR0aDozMTBweFwiIFwvPjxcL3A+XHJcblxyXG48cD5GaWd1cmUgNjogQW4gZXhhbXBsZSBzZXR0aW5nIGFuZCBpdHMgc29sdXRpb248XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBpbnB1dCBjb25zaXN0cyBvZiBtdWx0aXBsZSBkYXRhc2V0cywgZWFjaCBpbiB0aGUgZm9sbG93aW5nIGZvcm1hdC48XC9wPlxyXG5cclxuPHByZT5cclxubiBtXHJcbnJvdzxzdWI+MTxcL3N1Yj5cclxuLi4uXHJcbnJvdzxzdWI+bjxcL3N1Yj48XC9wcmU+XHJcblxyXG48cD5uIGlzIHRoZSBudW1iZXIgb2Ygcm93cyB3aGljaCBzYXRpc2ZpZXMgMiAmbGU7IG4gJmxlOyA5LiBtIGlzIHRoZSBudW1iZXIgb2YgY29sdW1ucyB3aGljaCBzYXRpc2ZpZXMgMiAmbGU7IG0gJmxlOyA5LiBFYWNoIHJvd2kgaXMgYSBzZXF1ZW5jZSBvZiBtIGRpZ2l0cyBzZXBhcmF0ZWQgYnkgYSBzcGFjZS4gVGhlIGRpZ2l0cyBtZWFuIHRoZSBmb2xsb3dpbmcuPFwvcD5cclxuXHJcbjxwPjA6IEVtcHR5PGJyIFwvPlxyXG4xOiBPY2N1cGllZCBieSBhbiBvYnN0YWNsZTxiciBcLz5cclxuMjogTWFya2VkIHdpdGggJnF1b3Q7MiZxdW90OzxiciBcLz5cclxuMzogTWFya2VkIHdpdGggJnF1b3Q7MyZxdW90OzxcL3A+XHJcblxyXG48cD5UaGUgZW5kIG9mIHRoZSBpbnB1dCBpcyBpbmRpY2F0ZWQgd2l0aCBhIGxpbmUgY29udGFpbmluZyB0d28gemVyb3Mgc2VwYXJhdGVkIGJ5IGEgc3BhY2U8XC9wPlxyXG5cclxuPHA+Jm5ic3A7PFwvcD5cclxuIiwib3V0cHV0IjoiPHA+Rm9yIGVhY2ggZGF0YXNldCwgb25lIGxpbmUgY29udGFpbmluZyB0aGUgbWluaW11bSB0b3RhbCBsZW5ndGggb2YgdGhlIHR3byBsaW5lcyBzaG91bGQgYmUgb3V0cHV0LiBJZiB0aGVyZSBpcyBubyBwYWlyIG9mIGxpbmVzIHNhdGlzZnlpbmcgdGhlIHJlcXVpcmVtZW50LCBhbnN3ZXIgJnF1b3Q7MCZxdW90OyBpbnN0ZWFkLiBObyBvdGhlciBjaGFyYWN0ZXJzIHNob3VsZCBiZSBjb250YWluZWQgaW4gdGhlIG91dHB1dDxcL3A+XHJcblxyXG48cD4mbmJzcDs8XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=