시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
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
W3sicHJvYmxlbV9pZCI6IjM5MDkiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWI5ZThcdWQ1NThcdWQwYzQgXHViYzMwXHVjMTIwIiwiZGVzY3JpcHRpb24iOiI8cD5cclxuXHRuICogbSBcdWNlNzhcdWM3M2NcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjOWM0IFx1YzljMVx1YzBhY1x1YWMwMVx1ZDYxNSBcdWM2MDFcdWM1ZWRcdWM3NzQgXHVjNzg4XHViMmU0LiBcdWM3NzQgXHVjOTExLCBcdWI0NTAgXHVjZTc4XHVjNzQwICZxdW90OzImcXVvdDtcdWI4NWMgXHVkNDVjXHVjMmRjXHViNDE4XHVjNWI0IFx1Yzc4OFx1YWNlMCwgXHViMmU0XHViOTc4IFx1YjQ1MCBcdWNlNzhcdWM3NDAgJnF1b3Q7MyZxdW90O1x1YzczY1x1Yjg1YyBcdWQ0NWNcdWMyZGNcdWI0MThcdWM1YjQgXHVjNzg4XHViMmU0LiBcdWM1YjRcdWI1YTQgXHVjZTc4XHVjNWQwXHViMjk0IFx1YzdhNVx1YzU2MFx1YmIzY1x1Yzc3NCBcdWM3ODhcdWIyZTQuIFx1Yzc3NFx1YjU0YywgXHViNDUwICZxdW90OzImcXVvdDtcdWM2NDAgXHViNDUwICZxdW90OzMmcXVvdDtcdWM3NDQgXHVhZDUwXHVjYzI4XHVkNTU4XHVjOWMwIFx1YzU0YVx1YjI5NCBcdWMxMjBcdWJkODRcdWM3M2NcdWI4NWMgXHVjNzc0XHVjNzNjXHViODI0XHVhY2UwIFx1ZDU1Y1x1YjJlNC4gXHVjMTIwXHVjNzQwIFx1YzdhNVx1YzU2MFx1YmIzY1x1Yzc3NCBcdWM1NDRcdWIyY2MgXHVjZTc4XHVjNzU4IFx1YzkxMVx1YzJlY1x1Yzc0NCBcdWFjMDBcdWI4NWMgXHViNjEwXHViMjk0IFx1YzEzOFx1Yjg1Y1x1Yjg1YyBcdWM1ZjBcdWFjYjBcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHJcblx0XHVkNTVjIFx1Y2U3OFx1YzVkMFx1YjI5NCBcdWNkNWNcdWIzMDAgMVx1YWMxY1x1Yzc1OCBcdWMxMjBcdWI5Y2MgXHVjNzg4XHVjNzQ0IFx1YzIxOCBcdWM3ODhcdWFjZTAsIFx1YzEyMFx1Yzc3NCBcdWMxMWNcdWI4NWMgXHVhZDUwXHVjYzI4XHVkNTYwXHVjMjE4XHViMjk0IFx1YzVjNlx1YjJlNC4gXHVjNzc0XHViNTRjLCBcdWI0NTAgXHVjMTIwXHVjNzU4IFx1YWUzOFx1Yzc3NFx1Yzc1OCBcdWQ1NjlcdWM3NzQgXHVjZDVjXHVjMThjXHVhYzAwIFx1YjQxOFx1YjI5NCBcdWFjODNcdWM3NDQgXHVjYzNlXHVjNzNjXHViODI0XHVhY2UwIFx1ZDU1Y1x1YjJlNC4gXHVjMTIwXHVjNzU4IFx1YWUzOFx1Yzc3NFx1YjI5NCBcdWMxMjBcdWM3NzQgXHVkMWI1XHVhY2ZjXHVkNTU4XHViMjk0IFx1Y2U3OFx1Yzc1OCBcdWFjYmRcdWFjYzRcdWM3NTggXHVhYzFjXHVjMjE4XHVjNzc0XHViMmU0LiBcdWM5ODksIFx1YWNiZFx1YWNjNFx1Yjk3YyBcdWFjZjVcdWM3MjBcdWQ1NThcdWIyOTQgXHViNDUwIFx1Y2U3OFx1Yzc0NCBcdWM3NzRcdWM3NDAgXHVjMTIwXHVjNzU4IFx1YWUzOFx1Yzc3NFx1YjI5NCAxXHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cclxuXHRcdWM1NDRcdWI3OTggXHVhZGY4XHViOWJjIChhKVx1YjI5NCBcdWM2MDFcdWM1ZWRcdWM3NTggXHVjNjA4XHVjMmRjXHVjNzc0XHVhY2UwLCAoYilcdWIyOTQgXHVjNzA0XHVjNzU4IFx1Yzg3MFx1YWM3NFx1Yzc0NCBcdWI5Y2NcdWM4NzFcdWQ1NThcdWFjOGMgXHVjMTIwXHVjNzQ0IFx1YWRmOFx1YjliMCBcdWFjODNcdWM3NzRcdWFjZTAsIFx1YWUzOFx1Yzc3NFx1YjI5NCAxOFx1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHJcblx0PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC9tYW4ucG5nXCIgc3R5bGU9XCJ3aWR0aDogMzEwcHg7IGhlaWdodDogMTY5cHg7XCIgXC8+PFwvcD5cclxuIiwiaW5wdXQiOiJcclxuPHA+XHJcblx0XHVjNzg1XHViODI1XHVjNzQwIFx1YzVlY1x1YjdlYyBcdWFjMWNcdWM3NTggXHViMzcwXHVjNzc0XHVkMTMwIFx1YzEzOFx1ZDJiOFx1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM4MzggXHVjNzg4XHViMmU0LiBcdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IFx1YjM3MFx1Yzc3NFx1ZDEzMCBcdWMxMzhcdWQyYjhcdWM3NTggXHVhYzFjXHVjMjE4IFRcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWIyZTRcdWM3NGMgXHVjOTA0XHViZDgwXHVkMTMwXHViMjk0IFx1YWMwMVx1YWMwMVx1Yzc1OCBcdWIzNzBcdWM3NzRcdWQxMzAgXHVjMTM4XHVkMmI4XHVjNzU4IFx1YzgxNVx1YmNmNFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzBcdWJhNzAsIFx1YjJlNFx1Yzc0Y1x1YWNmYyBcdWFjMTlcdWM3NzQgXHVhZDZjXHVjMTMxXHViNDE4XHVjNWI0XHVjODM4IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHJcblx0XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWQ1ODlcdWM3NTggXHVhYzFjXHVjMjE4IG5cdWFjZmMgXHVjNWY0XHVjNzU4IFx1YWMxY1x1YzIxOCBtXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKDIgJmxlOyBuICZsZTsgOSwgMiAmbGU7IG0gJmxlOyA5KSBcdWIyZTRcdWM3NGMgXHVjOTA0XHViZDgwXHVkMTMwIG5cdWFjMWNcdWM3NTggXHVjOTA0XHVjNWQwXHViMjk0IDFcdWQ1ODlcdWM3NTggXHVjODE1XHViY2Y0XHViZDgwXHVkMTMwIG5cdWQ1ODlcdWM3NTggXHVjODE1XHViY2Y0XHVhYzAwIFx1ZDU1YyBcdWM5MDRcdWM1ZDAgXHVkNTU4XHViMDk4XHVjMmRkIFx1YzhmY1x1YzViNFx1YzljMFx1YmE3MCwgbVx1YWMxY1x1Yzc1OCBcdWMyMmJcdWM3OTBcdWFjMDAgXHVhY2Y1XHViYzMxXHVjNzNjXHViODVjIFx1YWQ2Y1x1YmQ4NFx1YjQxOFx1YzViNCBcdWM3ODhcdWIyZTQuIFx1YzIyYlx1Yzc5MFx1Yzc1OCBcdWM3NThcdWJiZjhcdWIyOTQgXHViMmU0XHVjNzRjXHVhY2ZjIFx1YWMxOVx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHJcblx0MDogXHViZTQ4IFx1Y2U3ODxcL3A+XHJcbjxwPlxyXG5cdDE6IFx1YzdhNVx1YzU2MFx1YmIzYzxcL3A+XHJcbjxwPlxyXG5cdDI6ICZxdW90OzImcXVvdDtcdWI4NWMgXHVkNDVjXHVjMmRjXHViNDFjIFx1YWNmMzxcL3A+XHJcbjxwPlxyXG5cdDM6ICZxdW90OzMmcXVvdDtcdWM3M2NcdWI4NWMgXHVkNDVjXHVjMmRjXHViNDFjIFx1YWNmMzxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlxyXG5cdFx1YWMwMVx1YWMwMVx1Yzc1OCBcdWIzNzBcdWM3NzRcdWQxMzAgXHVjMTM4XHVkMmI4XHVjNWQwIFx1YjMwMFx1ZDU3NFx1YzExYywgXHViYjM4XHVjODFjXHVjNzU4IFx1Yzg3MFx1YWM3NFx1Yzc0NCBcdWI5Y2NcdWM4NzFcdWQ1NThcdWIyOTQgXHViNDUwIFx1YzEyMFx1Yzc1OCBcdWFlMzhcdWM3NzRcdWM3NTggXHVjZDVjXHVjMTlmXHVhYzEyXHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC4gXHViOWNjXHVjNTdkLCBcdWM4NzBcdWFjNzRcdWM3NDQgXHViOWNjXHVjODcxXHVkNTU4XHViMjk0IFx1YzEyMFx1Yzc0NCBcdWFkZjhcdWI5YjQgXHVjMjE4IFx1YzVjNlx1YjJlNFx1YmE3NCAmcXVvdDswJnF1b3Q7XHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIzOTA5IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiTWFuaGF0dGFuIFdpcmluZyIsImRlc2NyaXB0aW9uIjoiPHA+VGhlcmUgaXMgYSByZWN0YW5ndWxhciBhcmVhIGNvbnRhaW5pbmcgbiB4IG0gY2VsbHMuIFR3byBjZWxscyBhcmUgbWFya2VkIHdpdGggJnF1b3Q7MiZxdW90OywgYW5kIGFub3RoZXIgdHdvIHdpdGggJnF1b3Q7MyZxdW90Oy4gU29tZSBjZWxscyBhcmUgb2NjdXBpZWQgYnkgb2JzdGFjbGVzLiBZb3Ugc2hvdWxkIGNvbm5lY3QgdGhlIHR3byAmcXVvdDsyJnF1b3Q7cyBhbmQgYWxzbyB0aGUgdHdvICZxdW90OzMmcXVvdDtzIHdpdGggbm9uLWludGVyc2VjdGluZyBsaW5lcy4gTGluZXMgY2FuIHJ1biBvbmx5IHZlcnRpY2FsbHkgb3IgaG9yaXpvbnRhbGx5IGNvbm5lY3RpbmcgY2VudGVycyBvZiBjZWxscyB3aXRob3V0IG9ic3RhY2xlcy48XC9wPlxyXG5cclxuPHA+TGluZXMgY2Fubm90IHJ1biBvbiBhIGNlbGwgd2l0aCBhbiBvYnN0YWNsZS4gT25seSBvbmUgbGluZSBjYW4gcnVuIG9uIGEgY2VsbCBhdCBtb3N0IG9uY2UuIEhlbmNlLCBhIGxpbmUgY2Fubm90IGludGVyc2VjdCB3aXRoIHRoZSBvdGhlciBsaW5lLCBub3Igd2l0aCBpdHNlbGYuIFVuZGVyIHRoZXNlIGNvbnN0cmFpbnRzLCB0aGUgdG90YWwgbGVuZ3RoIG9mIHRoZSB0d28gbGluZXMgc2hvdWxkIGJlIG1pbmltaXplZC4gVGhlIGxlbmd0aCBvZiBhIGxpbmUgaXMgZGVmaW5lZCBhcyB0aGUgbnVtYmVyIG9mIGNlbGwgYm9yZGVycyBpdCBwYXNzZXMuIEluIHBhcnRpY3VsYXIsIGEgbGluZSBjb25uZWN0aW5nIGNlbGxzIHNoYXJpbmcgdGhlaXIgYm9yZGVyIGhhcyBsZW5ndGggMS48XC9wPlxyXG5cclxuPHA+RmlnLiA2KGEpIHNob3dzIGFuIGV4YW1wbGUgc2V0dGluZy4gRmlnLiA2KGIpIHNob3dzIHR3byBsaW5lcyBzYXRpc2Z5aW5nIHRoZSBjb25zdHJhaW50cyBhYm92ZSB3aXRoIG1pbmltdW0gdG90YWwgbGVuZ3RoIDE4LjxcL3A+XHJcblxyXG48cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL21hbi5wbmdcIiBzdHlsZT1cImhlaWdodDoxNjlweDsgd2lkdGg6MzEwcHhcIiBcLz48XC9wPlxyXG5cclxuPHA+RmlndXJlIDY6IEFuIGV4YW1wbGUgc2V0dGluZyBhbmQgaXRzIHNvbHV0aW9uPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgaW5wdXQgY29uc2lzdHMgb2YgbXVsdGlwbGUgZGF0YXNldHMsIGVhY2ggaW4gdGhlIGZvbGxvd2luZyBmb3JtYXQuPFwvcD5cclxuXHJcbjxwcmU+XHJcbm4gbVxyXG5yb3c8c3ViPjE8XC9zdWI+XHJcbi4uLlxyXG5yb3c8c3ViPm48XC9zdWI+PFwvcHJlPlxyXG5cclxuPHA+biBpcyB0aGUgbnVtYmVyIG9mIHJvd3Mgd2hpY2ggc2F0aXNmaWVzIDIgJmxlOyBuICZsZTsgOS4gbSBpcyB0aGUgbnVtYmVyIG9mIGNvbHVtbnMgd2hpY2ggc2F0aXNmaWVzIDIgJmxlOyBtICZsZTsgOS4gRWFjaCByb3dpIGlzIGEgc2VxdWVuY2Ugb2YgbSBkaWdpdHMgc2VwYXJhdGVkIGJ5IGEgc3BhY2UuIFRoZSBkaWdpdHMgbWVhbiB0aGUgZm9sbG93aW5nLjxcL3A+XHJcblxyXG48cD4wOiBFbXB0eTxiciBcLz5cclxuMTogT2NjdXBpZWQgYnkgYW4gb2JzdGFjbGU8YnIgXC8+XHJcbjI6IE1hcmtlZCB3aXRoICZxdW90OzImcXVvdDs8YnIgXC8+XHJcbjM6IE1hcmtlZCB3aXRoICZxdW90OzMmcXVvdDs8XC9wPlxyXG5cclxuPHA+VGhlIGVuZCBvZiB0aGUgaW5wdXQgaXMgaW5kaWNhdGVkIHdpdGggYSBsaW5lIGNvbnRhaW5pbmcgdHdvIHplcm9zIHNlcGFyYXRlZCBieSBhIHNwYWNlPFwvcD5cclxuXHJcbjxwPiZuYnNwOzxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPkZvciBlYWNoIGRhdGFzZXQsIG9uZSBsaW5lIGNvbnRhaW5pbmcgdGhlIG1pbmltdW0gdG90YWwgbGVuZ3RoIG9mIHRoZSB0d28gbGluZXMgc2hvdWxkIGJlIG91dHB1dC4gSWYgdGhlcmUgaXMgbm8gcGFpciBvZiBsaW5lcyBzYXRpc2Z5aW5nIHRoZSByZXF1aXJlbWVudCwgYW5zd2VyICZxdW90OzAmcXVvdDsgaW5zdGVhZC4gTm8gb3RoZXIgY2hhcmFjdGVycyBzaG91bGQgYmUgY29udGFpbmVkIGluIHRoZSBvdXRwdXQ8XC9wPlxyXG5cclxuPHA+Jm5ic3A7PFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d