시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 1187 276 183 26.715%

문제

상근이는 감옥에서 죄수 두 명을 탈옥시켜야 한다. 이 감옥은 1층짜리 건물이고, 상근이는 방금 평면도를 얻었다.

평면도에는 모든 벽과 문이 나타나있고, 탈옥시켜야 하는 죄수의 위치도 나타나 있다. 감옥은 무인 감옥으로 죄수 두 명이 감옥에 있는 유일한 사람이다.

문은 중앙 제어실에서만 열 수 있다. 상근이는 특별한 기술을 이용해 제어실을 통하지 않고 문을 열려고 한다. 하지만, 문을 열려면 시간이 매우 많이 걸린다. 두 죄수를 탈옥시키기 위해서 열어야 하는 문의 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수가 주어진다. 테스트 케이스의 수는 100개를 넘지 않는다.

첫째 줄에는 평면도의 높이 h와 너비 w가 주어진다. (2 ≤ h, w ≤ 100) 다음 h개 줄에는 감옥의 평면도 정보가 주어지며, 빈 공간은 '.', 지나갈 수 없는 벽은 '*', 문은 '#', 죄수의 위치는 '\$'이다.

상근이는 감옥 밖을 자유롭게 이동할 수 있고, 평면도에 표시된 죄수의 수는 항상 두 명이다. 각 죄수와 감옥의 바깥을 연결하는 경로가 항상 존재하는 경우만 입력으로 주어진다.

출력

각 테스트 케이스마다 두 죄수를 탈옥시키기 위해서 열어야 하는 문의 최소값을 출력한다.

예제 입력 1

3
5 9
****#****
*..#.#..*
****.****
*$#.#.#$*
*********
5 11
*#*********
*$*...*...*
*$*.*.*.*.*
*...*...*.*
*********.*
9 9
*#**#**#*
*#**#**#*
*#**#**#*
*#**.**#*
*#*#.#*#*
*$##*##$*
*#*****#*
*.#.#.#.*
*********

예제 출력 1

4
0
9
W3sicHJvYmxlbV9pZCI6IjkzNzYiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWQwYzhcdWM2MjUiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YzBjMVx1YWRmY1x1Yzc3NFx1YjI5NCBcdWFjMTBcdWM2MjVcdWM1ZDBcdWMxMWMgXHVjOGM0XHVjMjE4IFx1YjQ1MCBcdWJhODVcdWM3NDQgXHVkMGM4XHVjNjI1XHVjMmRjXHVjZjFjXHVjNTdjIFx1ZDU1Y1x1YjJlNC4gXHVjNzc0IFx1YWMxMFx1YzYyNVx1Yzc0MCAxXHVjZTM1XHVjOWRjXHViOWFjIFx1YWM3NFx1YmIzY1x1Yzc3NFx1YWNlMCwgXHVjMGMxXHVhZGZjXHVjNzc0XHViMjk0IFx1YmMyOVx1YWUwOCBcdWQzYzlcdWJhNzRcdWIzYzRcdWI5N2MgXHVjNWJiXHVjNWM4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWQzYzlcdWJhNzRcdWIzYzRcdWM1ZDBcdWIyOTQgXHViYWE4XHViNGUwIFx1YmNiZFx1YWNmYyBcdWJiMzhcdWM3NzQgXHViMDk4XHVkMGMwXHViMDk4XHVjNzg4XHVhY2UwLCBcdWQwYzhcdWM2MjVcdWMyZGNcdWNmMWNcdWM1N2MgXHVkNTU4XHViMjk0IFx1YzhjNFx1YzIxOFx1Yzc1OCBcdWM3MDRcdWNlNThcdWIzYzQgXHViMDk4XHVkMGMwXHViMDk4IFx1Yzc4OFx1YjJlNC4gXHVhYzEwXHVjNjI1XHVjNzQwIFx1YmIzNFx1Yzc3OCBcdWFjMTBcdWM2MjVcdWM3M2NcdWI4NWMgXHVjOGM0XHVjMjE4IFx1YjQ1MCBcdWJhODVcdWM3NzQgXHVhYzEwXHVjNjI1XHVjNWQwIFx1Yzc4OFx1YjI5NCBcdWM3MjBcdWM3N2NcdWQ1NWMgXHVjMGFjXHViNzhjXHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWJiMzhcdWM3NDAgXHVjOTExXHVjNTU5IFx1YzgxY1x1YzViNFx1YzJlNFx1YzVkMFx1YzExY1x1YjljYyBcdWM1ZjQgXHVjMjE4IFx1Yzc4OFx1YjJlNC4gXHVjMGMxXHVhZGZjXHVjNzc0XHViMjk0IFx1ZDJiOVx1YmNjNFx1ZDU1YyBcdWFlMzBcdWMyMjBcdWM3NDQgXHVjNzc0XHVjNmE5XHVkNTc0IFx1YzgxY1x1YzViNFx1YzJlNFx1Yzc0NCBcdWQxYjVcdWQ1NThcdWM5YzAgXHVjNTRhXHVhY2UwIFx1YmIzOFx1Yzc0NCBcdWM1ZjRcdWI4MjRcdWFjZTAgXHVkNTVjXHViMmU0LiBcdWQ1NThcdWM5YzBcdWI5Y2MsIFx1YmIzOFx1Yzc0NCBcdWM1ZjRcdWI4MjRcdWJhNzQgXHVjMmRjXHVhYzA0XHVjNzc0IFx1YjllNFx1YzZiMCBcdWI5Y2VcdWM3NzQgXHVhYzc4XHViOWIwXHViMmU0LiBcdWI0NTAgXHVjOGM0XHVjMjE4XHViOTdjIFx1ZDBjOFx1YzYyNVx1YzJkY1x1ZDBhNFx1YWUzMCBcdWM3MDRcdWQ1NzRcdWMxMWMgXHVjNWY0XHVjNWI0XHVjNTdjIFx1ZDU1OFx1YjI5NCBcdWJiMzhcdWM3NTggXHVhYzFjXHVjMjE4XHViOTdjIFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNzU4IFx1YWMxY1x1YzIxOFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM3NTggXHVjMjE4XHViMjk0IDEwMFx1YWMxY1x1Yjk3YyBcdWIxMThcdWM5YzAgXHVjNTRhXHViMjk0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IFx1ZDNjOVx1YmE3NFx1YjNjNFx1Yzc1OCZuYnNwO1x1YjE5Mlx1Yzc3NCBoXHVjNjQwIFx1YjEwOFx1YmU0NCB3XHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKDIgJmxlOyBoLCB3ICZsZTsgMTAwKSBcdWIyZTRcdWM3NGMgaFx1YWMxYyBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVhYzEwXHVjNjI1XHVjNzU4IFx1ZDNjOVx1YmE3NFx1YjNjNCBcdWM4MTVcdWJjZjRcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWMwXHViYTcwLCBcdWJlNDggXHVhY2Y1XHVhYzA0XHVjNzQwICYjMzk7LiYjMzk7LCBcdWM5YzBcdWIwOThcdWFjMDggXHVjMjE4IFx1YzVjNlx1YjI5NCBcdWJjYmRcdWM3NDAgJiMzOTsqJiMzOTssIFx1YmIzOFx1Yzc0MCAmIzM5OyMmIzM5OywgXHVjOGM0XHVjMjE4XHVjNzU4IFx1YzcwNFx1Y2U1OFx1YjI5NCAmIzM5O1xcJCYjMzk7XHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWMwYzFcdWFkZmNcdWM3NzRcdWIyOTQgXHVhYzEwXHVjNjI1IFx1YmMxNlx1Yzc0NCBcdWM3OTBcdWM3MjBcdWI4NmRcdWFjOGMgXHVjNzc0XHViM2Q5XHVkNTYwIFx1YzIxOCBcdWM3ODhcdWFjZTAsIFx1ZDNjOVx1YmE3NFx1YjNjNFx1YzVkMCBcdWQ0NWNcdWMyZGNcdWI0MWMgXHVjOGM0XHVjMjE4XHVjNzU4IFx1YzIxOFx1YjI5NCBcdWQ1NmRcdWMwYzEgXHViNDUwIFx1YmE4NVx1Yzc3NFx1YjJlNC4gXHVhYzAxIFx1YzhjNFx1YzIxOFx1YzY0MCBcdWFjMTBcdWM2MjVcdWM3NTggXHViYzE0XHVhZTY1XHVjNzQ0IFx1YzVmMFx1YWNiMFx1ZDU1OFx1YjI5NCBcdWFjYmRcdWI4NWNcdWFjMDAmbmJzcDtcdWQ1NmRcdWMwYzEgXHVjODc0XHVjN2FjXHVkNTU4XHViMjk0IFx1YWNiZFx1YzZiMFx1YjljYyBcdWM3ODVcdWI4MjVcdWM3M2NcdWI4NWMgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHViOWM4XHViMmU0IFx1YjQ1MCBcdWM4YzRcdWMyMThcdWI5N2MgXHVkMGM4XHVjNjI1XHVjMmRjXHVkMGE0XHVhZTMwIFx1YzcwNFx1ZDU3NFx1YzExYyBcdWM1ZjRcdWM1YjRcdWM1N2MgXHVkNTU4XHViMjk0IFx1YmIzOFx1Yzc1OCBcdWNkNWNcdWMxOGNcdWFjMTJcdWM3NDQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjkzNzYiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJKYWlsYnJlYWsiLCJkZXNjcmlwdGlvbiI6IjxwPkpvaG4gaXMgb24gYSBtaXNzaW9uIHRvIGdldCB0d28gcGVvcGxlIG91dCBvZiBwcmlzb24uIFRoaXMgcGFydGljdWxhciBwcmlzb24gaXMgYSBvbmUtc3RvcnkgYnVpbGRpbmcuIEhlIGhhcyBtYW5hZ2VkIHRvIGdldCBob2xkIG9mIGEgZGV0YWlsZWQgXHVmYjAyb29yIHBsYW4sIGluZGljYXRpbmcgYWxsIHRoZSB3YWxscyBhbmQgZG9vcnMuIEhlIGFsc28ga25vd3MgdGhlIGxvY2F0aW9ucyBvZiB0aGUgdHdvIHBlb3BsZSBoZSBuZWVkcyB0byBzZXQgZnJlZS4gVGhlIHByaXNvbiBndWFyZHMgYXJlIG5vdCB0aGUgcHJvYmxlbSAmbmRhc2g7IGhlIGhhcyBwbGFubmVkIGEgZGl2ZXJzaW9uIHRoYXQgc2hvdWxkIGxlYXZlIHRoZSBidWlsZGluZyBwcmFjdGljYWxseSB2b2lkLjxcL3A+XHJcblxyXG48cD5UaGUgZG9vcnMgYXJlIGhpcyBtYWluIGNvbmNlcm4uIEFsbCBkb29ycyBhcmUgbm9ybWFsbHkgb3BlbmVkIHJlbW90ZWx5IGZyb20gYSBjb250cm9sIHJvb20sIGJ1dCBKb2huIGNhbiBvcGVuIHRoZW0gYnkgb3RoZXIgbWVhbnMuIE9uY2UgaGUgaGFzIG1hbmFnZWQgdG8gb3BlbiBhIGRvb3IsIGl0IHJlbWFpbnMgb3Blbi4gSG93ZXZlciwgb3BlbmluZyBhIGRvb3IgdGFrZXMgdGltZSwgd2hpY2ggaGUgZG9lcyBub3QgaGF2ZSBtdWNoIG9mLCBzaW5jZSBoaXMgZGl2ZXJzaW9uIHdpbGwgb25seSB3b3JrIGZvciBzbyBsb25nLiBIZSB0aGVyZWZvcmUgd2FudHMgdG8gbWluaW1pemUgdGhlIG51bWJlciBvZiBkb29ycyBoZSBuZWVkcyB0byBvcGVuLiBDYW4geW91IGhlbHAgaGltIHBsYW4gdGhlIG9wdGltYWwgcm91dGUgdG8gZ2V0IHRvIHRoZSB0d28gcHJpc29uZXJzPzxcL3A+XHJcbiIsImlucHV0IjoiPHA+T24gdGhlIFx1ZmIwMXJzdCBsaW5lIG9uZSBwb3NpdGl2ZSBudW1iZXI6IHRoZSBudW1iZXIgb2YgdGVzdCBjYXNlcywgYXQgbW9zdCAxMDAuIEFmdGVyIHRoYXQgcGVyIHRlc3QgY2FzZTo8XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT5vbmUgbGluZSB3aXRoIHR3byBzcGFjZS1zZXBhcmF0ZWQgaW50ZWdlcnMgaCBhbmQgdyAoMiAmbGU7Jm5ic3A7aCwgdyAmbGU7Jm5ic3A7MTAwKTogdGhlIHdpZHRoIGFuZCBoZWlnaHQgb2YgdGhlIG1hcC48XC9saT5cclxuXHQ8bGk+aCBsaW5lcyB3aXRoIHcgY2hhcmFjdGVycyBkZXNjcmliaW5nIHRoZSBwcmlzb24gYnVpbGRpbmc6XHJcblx0PHVsPlxyXG5cdFx0PGxpPiZsc3F1bzsuJnJzcXVvOyBpcyBhbiBlbXB0eSBzcGFjZS48XC9saT5cclxuXHRcdDxsaT4mbHNxdW87KiZyc3F1bzsgaXMgYW4gaW1wZW5ldHJhYmxlIHdhbGwuPFwvbGk+XHJcblx0XHQ8bGk+JmxzcXVvOyMmcnNxdW87IGlzIGEgZG9vci48XC9saT5cclxuXHRcdDxsaT4mbHNxdW87XFwkJnJzcXVvOyBpcyBvbmUgb2YgdGhlIHR3byBwZW9wbGUgdG8gYmUgbGliZXJhdGVkLjxcL2xpPlxyXG5cdDxcL3VsPlxyXG5cdDxcL2xpPlxyXG48XC91bD5cclxuXHJcbjxwPkpvaG4gY2FuIGZyZWVseSBtb3ZlIGFyb3VuZCB0aGUgb3V0c2lkZSBvZiB0aGUgYnVpbGRpbmcuIFRoZXJlIGFyZSBleGFjdGx5IHR3byBwZW9wbGUgb24gdGhlIG1hcC4gRm9yIGVhY2ggcGVyc29uLCBhIHBhdGggZnJvbSB0aGUgb3V0c2lkZSB0byB0aGF0IHBlcnNvbiBpcyBndWFyYW50ZWVkIHRvIGV4aXN0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlBlciB0ZXN0IGNhc2U6PFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+b25lIGxpbmUgd2l0aCBhIHNpbmdsZSBpbnRlZ2VyOiB0aGUgbWluaW11bSBudW1iZXIgb2YgZG9vcnMgSm9obiBuZWVkcyB0byBvcGVuIGluIG9yZGVyIHRvIGdldCB0byBib3RoIHByaXNvbmVycy48XC9saT5cclxuPFwvdWw+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==