시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 256 MB115963326215825.925%

문제

상근이는 1층 빌딩에 침입해 매우 중요한 문서를 훔쳐오려고 한다. 상근이가 가지고 있는 평면도에는 문서의 위치가 모두 나타나 있다. 빌딩의 문은 모두 잠겨있기 때문에, 문을 열려면 열쇠가 필요하다. 상근이는 일부 열쇠를 이미 가지고 있고, 일부 열쇠는 빌딩의 바닥에 놓여져 있다. 상근이는 상하좌우로만 이동할 수 있다.

상근이가 훔칠 수 있는 문서의 최대 개수를 구하는 프로그램을 작성하시오.

입력

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

각 테스트 케이스의 첫째 줄에는 지도의 높이와 너비 h와 w (2 ≤ h, w ≤ 100)가 주어진다. 다음 h개 줄에는 빌딩을 나타내는 w개의 문자가 주어지며, 각 문자는 다음 중 하나이다.

  • '.'는 빈 공간을 나타낸다.
  • '*'는 벽을 나타내며, 상근이는 벽을 통과할 수 없다.
  • '\$'는 상근이가 훔쳐야하는 문서이다.
  • 알파벳 대문자는 문을 나타낸다.
  • 알파벳 소문자는 열쇠를 나타내며, 그 문자의 대문자인 모든 문을 열 수 있다.

마지막 줄에는 상근이가 이미 가지고 있는 열쇠가 공백없이 주어진다. 만약, 열쇠를 하나도 가지고 있지 않는 경우에는 "0"이 주어진다.

상근이는 처음에는 빌딩의 밖에 있으며, 빌딩 가장자리의 벽이 아닌 곳을 통해 빌딩 안팎을 드나들 수 있다. 각각의 문에 대해서, 그 문을 열 수 있는 열쇠의 개수는 0개, 1개, 또는 그 이상이고, 각각의 열쇠에 대해서, 그 열쇠로 열 수 있는 문의 개수도 0개, 1개, 또는 그 이상이다. 열쇠는 여러 번 사용할 수 있다.

출력

각 테스트 케이스 마다, 상근이가 훔칠 수 있는 문서의 최대 개수를 출력한다.

예제 입력 1

3
5 17
*****************
.............**$*
*B*A*P*C**X*Y*.X.
*y*x*a*p**$*$**$*
*****************
cz
5 11
*.*********
*...*...*x*
*X*.*.*.*.*
*$*...*...*
***********
0
7 7
*ABCDE*
X.....F
W.$$$.G
V.$$$.H
U.$$$.J
T.....K
*SQPML*
irony

예제 출력 1

3
1
0
W3sicHJvYmxlbV9pZCI6IjkzMjgiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWM1ZjRcdWMxZTAiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YzBjMVx1YWRmY1x1Yzc3NFx1YjI5NCZuYnNwOzFcdWNlMzUgXHViZTRjXHViNTI5XHVjNWQwIFx1Y2U2OFx1Yzc4NVx1ZDU3NCBcdWI5ZTRcdWM2YjAgXHVjOTExXHVjNjk0XHVkNTVjIFx1YmIzOFx1YzExY1x1Yjk3YyBcdWQ2ZDRcdWNjZDBcdWM2MjRcdWI4MjRcdWFjZTAgXHVkNTVjXHViMmU0LiBcdWMwYzFcdWFkZmNcdWM3NzRcdWFjMDAgXHVhYzAwXHVjOWMwXHVhY2UwIFx1Yzc4OFx1YjI5NCBcdWQzYzlcdWJhNzRcdWIzYzRcdWM1ZDBcdWIyOTQgXHViYjM4XHVjMTFjXHVjNzU4IFx1YzcwNFx1Y2U1OFx1YWMwMCBcdWJhYThcdWI0NTAgXHViMDk4XHVkMGMwXHViMDk4IFx1Yzc4OFx1YjJlNC4gXHViZTRjXHViNTI5XHVjNzU4IFx1YmIzOFx1Yzc0MCBcdWJhYThcdWI0NTAgXHVjN2EwXHVhY2E4XHVjNzg4XHVhZTMwIFx1YjU0Y1x1YmIzOFx1YzVkMCwgXHViYjM4XHVjNzQ0IFx1YzVmNFx1YjgyNFx1YmE3NCBcdWM1ZjRcdWMxZTBcdWFjMDAgXHVkNTQ0XHVjNjk0XHVkNTU4XHViMmU0LiBcdWMwYzFcdWFkZmNcdWM3NzRcdWIyOTQgXHVjNzdjXHViZDgwIFx1YzVmNFx1YzFlMFx1Yjk3YyBcdWM3NzRcdWJiZjggXHVhYzAwXHVjOWMwXHVhY2UwIFx1Yzc4OFx1YWNlMCwgXHVjNzdjXHViZDgwIFx1YzVmNFx1YzFlMFx1YjI5NCBcdWJlNGNcdWI1MjlcdWM3NTggXHViYzE0XHViMmU1XHVjNWQwIFx1YjE5M1x1YzVlY1x1YzgzOCBcdWM3ODhcdWIyZTQuIFx1YzBjMVx1YWRmY1x1Yzc3NFx1YjI5NCBcdWMwYzFcdWQ1NThcdWM4OGNcdWM2YjBcdWI4NWNcdWI5Y2MgXHVjNzc0XHViM2Q5XHVkNTYwJm5ic3A7XHVjMjE4IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjMGMxXHVhZGZjXHVjNzc0XHVhYzAwIFx1ZDZkNFx1Y2U2MCBcdWMyMTggXHVjNzg4XHViMjk0IFx1YmIzOFx1YzExY1x1Yzc1OCBcdWNkNWNcdWIzMDAgXHVhYzFjXHVjMjE4XHViOTdjIFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNzU4IFx1YWMxY1x1YzIxOFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM3NTggXHVjMjE4XHViMjk0IDEwMFx1YWMxY1x1Yjk3YyBcdWIxMThcdWM5YzAgXHVjNTRhXHViMjk0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yzc1OCBcdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IFx1YzljMFx1YjNjNFx1Yzc1OCBcdWIxOTJcdWM3NzRcdWM2NDAgXHViMTA4XHViZTQ0IGhcdWM2NDAgdyAoMiAmbGU7IGgsIHcgJmxlOyAxMDApXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHViMmU0XHVjNzRjIGhcdWFjMWMgXHVjOTA0XHVjNWQwXHViMjk0IFx1YmU0Y1x1YjUyOVx1Yzc0NCBcdWIwOThcdWQwYzBcdWIwYjRcdWIyOTQgd1x1YWMxY1x1Yzc1OCBcdWJiMzhcdWM3OTBcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWMwXHViYTcwLCBcdWFjMDEgXHViYjM4XHVjNzkwXHViMjk0IFx1YjJlNFx1Yzc0YyBcdWM5MTEgXHVkNTU4XHViMDk4XHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPiYjMzk7LiYjMzk7XHViMjk0IFx1YmU0OCBcdWFjZjVcdWFjMDRcdWM3NDQgXHViMDk4XHVkMGMwXHViMGI4XHViMmU0LjxcL2xpPlxyXG5cdDxsaT4mIzM5OyomIzM5O1x1YjI5NCBcdWJjYmRcdWM3NDQgXHViMDk4XHVkMGMwXHViMGI0XHViYTcwLCBcdWMwYzFcdWFkZmNcdWM3NzRcdWIyOTQgXHViY2JkXHVjNzQ0IFx1ZDFiNVx1YWNmY1x1ZDU2MCBcdWMyMTggXHVjNWM2XHViMmU0LjxcL2xpPlxyXG5cdDxsaT4mIzM5O1xcJCYjMzk7XHViMjk0IFx1YzBjMVx1YWRmY1x1Yzc3NFx1YWMwMCBcdWQ2ZDRcdWNjZDBcdWM1N2NcdWQ1NThcdWIyOTQgXHViYjM4XHVjMTFjXHVjNzc0XHViMmU0LjxcL2xpPlxyXG5cdDxsaT5cdWM1NGNcdWQzMGNcdWJjYjMgXHViMzAwXHViYjM4XHVjNzkwXHViMjk0IFx1YmIzOFx1Yzc0NCBcdWIwOThcdWQwYzBcdWIwYjhcdWIyZTQuPFwvbGk+XHJcblx0PGxpPlx1YzU0Y1x1ZDMwY1x1YmNiMyBcdWMxOGNcdWJiMzhcdWM3OTBcdWIyOTQgXHVjNWY0XHVjMWUwXHViOTdjIFx1YjA5OFx1ZDBjMFx1YjBiNFx1YmE3MCwgXHVhZGY4IFx1YmIzOFx1Yzc5MFx1Yzc1OCBcdWIzMDBcdWJiMzhcdWM3OTBcdWM3NzggXHViYWE4XHViNGUwIFx1YmIzOFx1Yzc0NCBcdWM1ZjQgXHVjMjE4IFx1Yzc4OFx1YjJlNC48XC9saT5cclxuPFwvdWw+XHJcblxyXG48cD5cdWI5YzhcdWM5YzBcdWI5YzkgXHVjOTA0XHVjNWQwXHViMjk0IFx1YzBjMVx1YWRmY1x1Yzc3NFx1YWMwMCBcdWM3NzRcdWJiZjggXHVhYzAwXHVjOWMwXHVhY2UwIFx1Yzc4OFx1YjI5NCBcdWM1ZjRcdWMxZTBcdWFjMDAgXHVhY2Y1XHViYzMxXHVjNWM2XHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHViOWNjXHVjNTdkLCBcdWM1ZjRcdWMxZTBcdWI5N2MgXHVkNTU4XHViMDk4XHViM2M0IFx1YWMwMFx1YzljMFx1YWNlMCBcdWM3ODhcdWM5YzAgXHVjNTRhXHViMjk0IFx1YWNiZFx1YzZiMFx1YzVkMFx1YjI5NCAmcXVvdDswJnF1b3Q7XHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjMGMxXHVhZGZjXHVjNzc0XHViMjk0IFx1Y2M5OFx1Yzc0Y1x1YzVkMFx1YjI5NCBcdWJlNGNcdWI1MjlcdWM3NTggXHViYzE2XHVjNWQwIFx1Yzc4OFx1YzczY1x1YmE3MCwgXHViZTRjXHViNTI5IFx1YWMwMFx1YzdhNVx1Yzc5MFx1YjlhY1x1Yzc1OCBcdWJjYmRcdWM3NzQgXHVjNTQ0XHViMmNjIFx1YWNmM1x1Yzc0NCBcdWQxYjVcdWQ1NzQgXHViZTRjXHViNTI5IFx1YzU0OFx1ZDMwZVx1Yzc0NCBcdWI0ZGNcdWIwOThcdWI0ZTQgXHVjMjE4IFx1Yzc4OFx1YjJlNC4gXHVhYzAxXHVhYzAxXHVjNzU4IFx1YmIzOFx1YzVkMCBcdWIzMDBcdWQ1NzRcdWMxMWMsIFx1YWRmOCBcdWJiMzhcdWM3NDQgXHVjNWY0IFx1YzIxOCBcdWM3ODhcdWIyOTQgXHVjNWY0XHVjMWUwXHVjNzU4IFx1YWMxY1x1YzIxOFx1YjI5NCAwXHVhYzFjLCAxXHVhYzFjLCBcdWI2MTBcdWIyOTQgXHVhZGY4IFx1Yzc3NFx1YzBjMVx1Yzc3NFx1YWNlMCwgXHVhYzAxXHVhYzAxXHVjNzU4IFx1YzVmNFx1YzFlMFx1YzVkMCBcdWIzMDBcdWQ1NzRcdWMxMWMsIFx1YWRmOCBcdWM1ZjRcdWMxZTBcdWI4NWMgXHVjNWY0IFx1YzIxOCBcdWM3ODhcdWIyOTQgXHViYjM4XHVjNzU4IFx1YWMxY1x1YzIxOFx1YjNjNCAwXHVhYzFjLCAxXHVhYzFjLCBcdWI2MTBcdWIyOTQgXHVhZGY4IFx1Yzc3NFx1YzBjMVx1Yzc3NFx1YjJlNC4gXHVjNWY0XHVjMWUwXHViMjk0IFx1YzVlY1x1YjdlYyBcdWJjODggXHVjMGFjXHVjNmE5XHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTQgXHViOWM4XHViMmU0LCBcdWMwYzFcdWFkZmNcdWM3NzRcdWFjMDAgXHVkNmQ0XHVjZTYwIFx1YzIxOCBcdWM3ODhcdWIyOTQgXHViYjM4XHVjMTFjXHVjNzU4IFx1Y2Q1Y1x1YjMwMCBcdWFjMWNcdWMyMThcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IktvcmVhbiJ9LHsicHJvYmxlbV9pZCI6IjkzMjgiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJLZXlzIiwiZGVzY3JpcHRpb24iOiI8cD5Kb2huIGlzIG9uIGEgbWlzc2lvbiB0byBzdGVhbCBzb21lIGRvY3VtZW50cyBvZiBpbXBvcnRhbmNlIGZyb20gYSBvbmUtc3RvcnkgYnVpbGRpbmcuIEhlIGhhcyBtYW5hZ2VkIHRvIGdldCBob2xkIG9mIGEgZGV0YWlsZWQgXHVmYjAyb29yIHBsYW4gb2YgdGhlIGJ1aWxkaW5nLCBpbmRpY2F0aW5nIHRoZSBsb2NhdGlvbnMgb2YgYWxsIHRoZSBkb2N1bWVudHMuIFRoZXJlIGFyZSBkb29ycyBpbiB0aGUgYnVpbGRpbmcgdGhhdCByZXF1aXJlIGEga2V5IHRvIGJlIG9wZW5lZC4gSm9obiBoYXMgc29tZSBrZXlzIGluIGhpcyBwb3NzZXNzaW9uLCBhbmQgdGhlcmUgYXJlIHNvbWUga2V5cyBpbiB0aGUgYnVpbGRpbmcgaXRzZWxmLiBDYW4geW91IGhlbHAgaGltIFx1ZmIwMWd1cmUgb3V0IGhvdyBtYW55IGRvY3VtZW50cyBoZSBjYW4gc3RlYWw/PFwvcD5cclxuIiwiaW5wdXQiOiI8cD5PbiB0aGUgXHVmYjAxcnN0IGxpbmUgb25lIHBvc2l0aXZlIG51bWJlcjogdGhlIG51bWJlciBvZiB0ZXN0IGNhc2VzLCBhdCBtb3N0IDEwMC4gQWZ0ZXIgdGhhdCBwZXIgdGVzdCBjYXNlOjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPm9uZSBsaW5lIHdpdGggdHdvIHNwYWNlLXNlcGFyYXRlZCBpbnRlZ2VycyBoIGFuZCB3ICgyICZsZTsgaCwgdyAmbGU7IDEwMCk6IHRoZSBoZWlnaHQgYW5kIHdpZHRoIG9mIHRoZSBtYXAuPFwvbGk+XHJcblx0PGxpPmggbGluZXMgd2l0aCB3IGNoYXJhY3RlcnMgZGVzY3JpYmluZyB0aGUgYnVpbGRpbmc6XHJcblx0PHVsPlxyXG5cdFx0PGxpPiZyc3F1bzsuJnJzcXVvOyBpcyBhbiBlbXB0eSBzcGFjZS48XC9saT5cclxuXHRcdDxsaT4mcnNxdW87KiZyc3F1bzsgaXMgYW4gaW1wZW5ldHJhYmxlIHdhbGwuPFwvbGk+XHJcblx0XHQ8bGk+JnJzcXVvO1xcJCZyc3F1bzsgaXMgYSBkb2N1bWVudCB0aGF0IEpvaG4gd291bGQgbGlrZSB0byBzdGVhbC48XC9saT5cclxuXHRcdDxsaT5hbiB1cHBlcmNhc2UgbGV0dGVyIGlzIGEgZG9vci48XC9saT5cclxuXHRcdDxsaT5hIGxvd2VyY2FzZSBsZXR0ZXIgaXMgYSBrZXkgdGhhdCBvcGVucyBhbGwgZG9vcnMgY29ycmVzcG9uZGluZyB0byBpdHMgdXBwZXJjYXNlIGVxdWl2YWxlbnQuPFwvbGk+XHJcblx0PFwvdWw+XHJcblx0PFwvbGk+XHJcblx0PGxpPm9uZSBsaW5lIHdpdGggYSBzdHJpbmcgY29uc2lzdGluZyBvZiBkaXN0aW5jdCBsb3dlcmNhc2UgbGV0dGVyczogdGhlIGtleXMgdGhhdCBKb2huIGhhcyBpbiBoaXMgcG9zc2Vzc2lvbi4gSWYgaGUgaGFzIG5vIGtleXMsIHRoZSBsaW5lIGNvbnRhaW5zICZsZHF1bzswJnJkcXVvOyBpbnN0ZWFkLjxcL2xpPlxyXG48XC91bD5cclxuXHJcbjxwPkpvaG4gY2FuIGZyZWVseSBtb3ZlIGFyb3VuZCB0aGUgb3V0c2lkZSBvZiB0aGUgYnVpbGRpbmcuIEZvciBhbnkgZ2l2ZW4gZG9vciwgdGhlIG51bWJlciBvZiBhdmFpbGFibGUga2V5cyB0aGF0IG9wZW4gaXQgY2FuIGJlIHplcm8sIG9uZSwgb3IgbW9yZSB0aGFuIG9uZS4gRm9yIGFueSBnaXZlbiBrZXksIHRoZSBudW1iZXIgb2YgZG9vcnMgdGhhdCBpdCBvcGVucyBjYW4gYmUgemVybywgb25lIG9yIG1vcmUgdGhhbiBvbmUuIEtleXMgY2FuIGJlIHJldXNlZC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5QZXIgdGVzdCBjYXNlOjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPm9uZSBsaW5lIHdpdGggYW4gaW50ZWdlcjogdGhlIHRvdGFsIG51bWJlciBvZiBkb2N1bWVudHMgdGhhdCBKb2huIGNhbiBzdGVhbC48XC9saT5cclxuPFwvdWw+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IkVuZ2xpc2gifV0=

출처

ICPC > Regionals > Europe > Northwestern European Regional Contest > Benelux Algorithm Programming Contest > BAPC 2013 Preliminaries K번