시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 61 21 15 32.609%

문제

상근이는 사람들에게 수영장을 만들어주고 있다. 이번에는 정인이의 앞 마당에 수영장을 만들어 주려고 한다.

수영장 부지는 w×h크기이고, 1×1 크기의 정사각형 구역으로 나누어져 있다.수영장은 0개 또는 그 이상의 구멍 구역으로 이루어져 있다. 구멍을 뚫은 곳에는 나중에 물이 채워질 예정이다.

수영장을 만들기 전에 각 구역은 구멍('.')이거나 잔디('#')이다. 이 땅을 수영장으로 만드려면 아래와 같은 규칙을 지켜야 한다.

  • 구역을 그 자체로 놔둘 수 있다. 이때 드는 비용은 없다.
  • 잔디였던 구역에 구멍을 파는데 드는 비용은 d원이다.
  • 구멍이였던 구역에 구멍을 막고 잔디를 심는데 드는 비용은 f원이다.
  • 수영장의 경계가 되는 각 변(잔디와 구멍 사이)에는 물이 세지 않기 위한 경계 처리를 해야 한다. 이 작업은 한 변당 b원이 든다.
  • 수영장 부지의 가장 바깥 행과 열은 잔디이어야 한다.

현재 수영장 부지의 땅 정보가 주어졌을 때, 수영장을 만드는데 가장 싼 비용을 구하는 프로그램을 작성하시오.

입력

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

각 테스트 케이스의 첫째 줄에는 수영장 부지의 크기 w와 h가 주어진다. (2 ≤ w, h ≤ 50) 다음 줄에는 d, f, b가 주어진다. (1 ≤ d, f, b ≤ 10,000) 다음 h개 줄에는 수영장을 만들 부지의 정보가 주어진다.

출력

각 테스트 케이스에 대해서, 수영장을 만드는데 드는 비용의 최솟값을 출력한다. 

예제 입력 1

3
3 3
5 5 1
#.#
#.#
###
5 4
1 8 1
#..##
##.##
#.#.#
#####
2 2
27 11 11
#.
.#

예제 출력 1

9
27
22
W3sicHJvYmxlbV9pZCI6IjM2NTYiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWMyMThcdWM2MDFcdWM3YTUgXHViOWNjXHViNGU0XHVhZTMwIiwiZGVzY3JpcHRpb24iOiI8cD5cdWMwYzFcdWFkZmNcdWM3NzRcdWIyOTQgXHVjMGFjXHViNzhjXHViNGU0XHVjNWQwXHVhYzhjIFx1YzIxOFx1YzYwMVx1YzdhNVx1Yzc0NCBcdWI5Y2NcdWI0ZTRcdWM1YjRcdWM4ZmNcdWFjZTAgXHVjNzg4XHViMmU0LiBcdWM3NzRcdWJjODhcdWM1ZDBcdWIyOTQgXHVjODE1XHVjNzc4XHVjNzc0XHVjNzU4IFx1YzU1ZSBcdWI5YzhcdWIyZjlcdWM1ZDAgXHVjMjE4XHVjNjAxXHVjN2E1XHVjNzQ0IFx1YjljY1x1YjRlNFx1YzViNCBcdWM4ZmNcdWI4MjRcdWFjZTAgXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWMyMThcdWM2MDFcdWM3YTUgXHViZDgwXHVjOWMwXHViMjk0Jm5ic3A7dyZ0aW1lcztoXHVkMDZjXHVhZTMwXHVjNzc0XHVhY2UwLCAxJnRpbWVzOzEgXHVkMDZjXHVhZTMwXHVjNzU4IFx1YzgxNVx1YzBhY1x1YWMwMVx1ZDYxNSBcdWFkNmNcdWM1ZWRcdWM3M2NcdWI4NWMgXHViMDk4XHViMjA0XHVjNWI0XHVjODM4IFx1Yzc4OFx1YjJlNC5cdWMyMThcdWM2MDFcdWM3YTVcdWM3NDAgMFx1YWMxYyZuYnNwO1x1YjYxMFx1YjI5NCBcdWFkZjggXHVjNzc0XHVjMGMxXHVjNzU4IFx1YWQ2Y1x1YmE0ZCBcdWFkNmNcdWM1ZWRcdWM3M2NcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjODM4IFx1Yzc4OFx1YjJlNC4gXHVhZDZjXHViYTRkXHVjNzQ0IFx1YjZhYlx1Yzc0MCBcdWFjZjNcdWM1ZDBcdWIyOTQgXHViMDk4XHVjOTExXHVjNWQwIFx1YmIzY1x1Yzc3NCBcdWNjNDRcdWM2Y2NcdWM5YzggXHVjNjA4XHVjODE1XHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWMyMThcdWM2MDFcdWM3YTVcdWM3NDQgXHViOWNjXHViNGU0XHVhZTMwIFx1YzgwNFx1YzVkMCBcdWFjMDEgXHVhZDZjXHVjNWVkXHVjNzQwIFx1YWQ2Y1x1YmE0ZCgmIzM5Oy4mIzM5OylcdWM3NzRcdWFjNzBcdWIwOTggXHVjNzk0XHViNTE0KCYjMzk7IyYjMzk7KVx1Yzc3NFx1YjJlNC4gXHVjNzc0IFx1YjU0NVx1Yzc0NCBcdWMyMThcdWM2MDFcdWM3YTVcdWM3M2NcdWI4NWMgXHViOWNjXHViNGRjXHViODI0XHViYTc0IFx1YzU0NFx1Yjc5OFx1YzY0MCBcdWFjMTlcdWM3NDAgXHVhZGRjXHVjZTU5XHVjNzQ0IFx1YzljMFx1Y2YxY1x1YzU3YyBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+XHVhZDZjXHVjNWVkXHVjNzQ0IFx1YWRmOCBcdWM3OTBcdWNjYjRcdWI4NWMgXHViMTk0XHViNDU4IFx1YzIxOCBcdWM3ODhcdWIyZTQuIFx1Yzc3NFx1YjU0YyBcdWI0ZGNcdWIyOTQgXHViZTQ0XHVjNmE5XHVjNzQwIFx1YzVjNlx1YjJlNC48XC9saT5cclxuXHQ8bGk+XHVjNzk0XHViNTE0XHVjNjAwXHViMzU4IFx1YWQ2Y1x1YzVlZFx1YzVkMCBcdWFkNmNcdWJhNGRcdWM3NDQgXHVkMzBjXHViMjk0XHViMzcwIFx1YjRkY1x1YjI5NCBcdWJlNDRcdWM2YTlcdWM3NDAgZFx1YzZkMFx1Yzc3NFx1YjJlNC48XC9saT5cclxuXHQ8bGk+XHVhZDZjXHViYTRkXHVjNzc0XHVjNjAwXHViMzU4IFx1YWQ2Y1x1YzVlZFx1YzVkMCBcdWFkNmNcdWJhNGRcdWM3NDQgXHViOWM5XHVhY2UwIFx1Yzc5NFx1YjUxNFx1Yjk3YyBcdWMyZWNcdWIyOTRcdWIzNzAgXHViNGRjXHViMjk0IFx1YmU0NFx1YzZhOVx1Yzc0MCBmXHVjNmQwXHVjNzc0XHViMmU0LjxcL2xpPlxyXG5cdDxsaT5cdWMyMThcdWM2MDFcdWM3YTVcdWM3NTggXHVhY2JkXHVhY2M0XHVhYzAwIFx1YjQxOFx1YjI5NCBcdWFjMDEgXHViY2MwKFx1Yzc5NFx1YjUxNFx1YzY0MCBcdWFkNmNcdWJhNGQgXHVjMGFjXHVjNzc0KVx1YzVkMFx1YjI5NCBcdWJiM2NcdWM3NzQgXHVjMTM4XHVjOWMwIFx1YzU0YVx1YWUzMCBcdWM3MDRcdWQ1NWMgXHVhY2JkXHVhY2M0IFx1Y2M5OFx1YjlhY1x1Yjk3YyBcdWQ1NzRcdWM1N2MgXHVkNTVjXHViMmU0LiBcdWM3NzQgXHVjNzkxXHVjNWM1XHVjNzQwIFx1ZDU1YyBcdWJjYzBcdWIyZjkgYlx1YzZkMFx1Yzc3NCBcdWI0ZTBcdWIyZTQuPFwvbGk+XHJcblx0PGxpPlx1YzIxOFx1YzYwMVx1YzdhNSBcdWJkODBcdWM5YzBcdWM3NTggXHVhYzAwXHVjN2E1IFx1YmMxNFx1YWU2NSBcdWQ1ODlcdWFjZmMgXHVjNWY0XHVjNzQwIFx1Yzc5NFx1YjUxNFx1Yzc3NFx1YzViNFx1YzU3YyBcdWQ1NWNcdWIyZTQuPFwvbGk+XHJcbjxcL3VsPlxyXG5cclxuPHA+XHVkNjA0XHVjN2FjIFx1YzIxOFx1YzYwMVx1YzdhNSBcdWJkODBcdWM5YzBcdWM3NTggXHViNTQ1Jm5ic3A7XHVjODE1XHViY2Y0XHVhYzAwIFx1YzhmY1x1YzViNFx1Yzg0Y1x1Yzc0NCBcdWI1NGMsIFx1YzIxOFx1YzYwMVx1YzdhNVx1Yzc0NCBcdWI5Y2NcdWI0ZGNcdWIyOTRcdWIzNzAgXHVhYzAwXHVjN2E1IFx1YzJmYyBcdWJlNDRcdWM2YTlcdWM3NDQgXHVhZDZjXHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM3NTggXHVhYzFjXHVjMjE4XHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yzc1OCBcdWFjMWNcdWMyMThcdWIyOTQgMTAwXHVhYzFjXHViOTdjIFx1YjExOFx1YzljMCBcdWM1NGFcdWIyOTRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNzU4IFx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQmbmJzcDtcdWMyMThcdWM2MDFcdWM3YTUgXHViZDgwXHVjOWMwXHVjNzU4IFx1ZDA2Y1x1YWUzMCZuYnNwO3dcdWM2NDAgaFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgyICZsZTsgdywgaCAmbGU7IDUwKSBcdWIyZTRcdWM3NGMgXHVjOTA0XHVjNWQwXHViMjk0IGQsIGYsIGJcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoMSAmbGU7IGQsIGYsIGIgJmxlOyAxMCwwMDApIFx1YjJlNFx1Yzc0YyBoXHVhYzFjIFx1YzkwNFx1YzVkMFx1YjI5NCBcdWMyMThcdWM2MDFcdWM3YTVcdWM3NDQgXHViOWNjXHViNGU0IFx1YmQ4MFx1YzljMFx1Yzc1OCBcdWM4MTVcdWJjZjRcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNWQwIFx1YjMwMFx1ZDU3NFx1YzExYywgXHVjMjE4XHVjNjAxXHVjN2E1XHVjNzQ0IFx1YjljY1x1YjRkY1x1YjI5NFx1YjM3MCBcdWI0ZGNcdWIyOTQgXHViZTQ0XHVjNmE5XHVjNzU4IFx1Y2Q1Y1x1YzE5Zlx1YWMxMlx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuJm5ic3A7PFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiMzY1NiIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IlBvb2wgY29uc3RydWN0aW9uIiwiZGVzY3JpcHRpb24iOiI8cD5Zb3UgYXJlIHdvcmtpbmcgZm9yIHRoZSBJbnRlcm5hdGlvbmFsIENvbXBhbnkgZm9yIFBvb2wgQ29uc3RydWN0aW9uLCBhIGNvbnN0cnVjdGlvbiBjb21wYW55IHdoaWNoIHNwZWNpYWxpemVzIGluIGJ1aWxkaW5nIHN3aW1taW5nIHBvb2xzLiBBIG5ldyBjbGllbnQgd2FudHMgdG8gYnVpbGQgc2V2ZXJhbCBuZXcgcG9vbCBhcmVhcy48XC9wPlxyXG5cclxuPHA+QSBwb29sIGFyZWEgaXMgYSByZWN0YW5ndWxhciBncmlkIG9mIHcgJnRpbWVzOyZuYnNwO2ggc3F1YXJlIHBhdGNoZXMsIGNvbnNpc3Rpbmcgb2YgemVybyBvciBtb3JlIChwb3NzaWJseSBkaXNjb25uZWN0ZWQpIHBvb2xzLiBBIHBvb2wgY29uc2lzdHMgb2Ygb25lIG9yIG11bHRpcGxlIGNvbm5lY3RlZCBob2xlIHBhdGNoZXMsIHdoaWNoIHdpbGwgbGF0ZXIgYmUgXHVmYjAxbGxlZCB3aXRoIHdhdGVyLiBJbiB0aGUgYmVnaW5uaW5nLCB5b3Ugc3RhcnQgd2l0aCBhIHBpZWNlIG9mIGxhbmQgd2hlcmUgZWFjaCBwYXRjaCBpcyBlaXRoZXIgYSBob2xlIGluIHRoZSBncm91bmQgKCZyc3F1bzsuJnJzcXVvOykgb3IgXHVmYjAyYXQgZ3Jhc3MgKCZyc3F1bzsjJnJzcXVvOykuIEluIG9yZGVyIHRvIHRyYW5zZm9ybSB0aGlzIGxhbmQgaW50byBhIHBvb2wgYXJlYSwgeW91IG11c3QgYWRoZXJlIHRvIHRoZSBmb2xsb3dpbmc6PFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+WW91IGNhbiBsZWF2ZSBhIHBhdGNoIGFzIGl0IGlzLiBUaGlzIGNvc3RzIG5vdGhpbmcuPFwvbGk+XHJcblx0PGxpPklmIHRoZSBwYXRjaCBpcyBncmFzcyBpbiB0aGUgYmVnaW5uaW5nLCB5b3UgY2FuIGRpZyBhIGhvbGUgdGhlcmUuIFRoaXMgY29zdHMgZCBFVVIuPFwvbGk+XHJcblx0PGxpPklmIHRoZSBwYXRjaCBpcyBhIGhvbGUgaW4gdGhlIGJlZ2lubmluZywgeW91IGNhbiBcdWZiMDFsbCB0aGUgaG9sZSBhbmQgcHV0IGdyYXNzIG9uIHRvcC4gVGhpcyBjb3N0cyBmIEVVUi48XC9saT5cclxuXHQ8bGk+WW91IG11c3QgcGxhY2Ugc3BlY2lhbCBib3VuZGFyeSBlbGVtZW50cyBhbG9uZyBlYWNoIGVkZ2UgcnVubmluZyBiZXR3ZWVuIGEgXHVmYjAxbmFsIGdyYXNzIHBhdGNoIGFuZCBhIFx1ZmIwMW5hbCBob2xlIHBhdGNoLCB0byBlbnN1cmUgdGhhdCB3YXRlciBkb2VzIG5vdCBsZWFrIGZyb20gdGhlIHBvb2wuIFRoaXMgY29zdHMgYiBFVVIgcGVyIGJvdW5kYXJ5IGVsZW1lbnQuPFwvbGk+XHJcblx0PGxpPlRoZSBvdXRlcm1vc3Qgcm93cyBhbmQgY29sdW1ucyBvZiB0aGUgcG9vbCBhcmVhIG11c3QgYWx3YXlzIGJlIGdyYXNzLjxcL2xpPlxyXG48XC91bD5cclxuXHJcbjxwPllvdSBhcmUgZ2l2ZW4gdGhlIHRhc2sgb2YgY2FsY3VsYXRpbmcgdGhlIGNvc3Qgb2YgdGhlIGNoZWFwZXN0IHBvc3NpYmxlIHBvb2wgYXJlYSBnaXZlbiB0aGUgbGF5b3V0IG9mIHRoZSBleGlzdGluZyBwaWVjZSBvZiBsYW5kLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+T24gdGhlIFx1ZmIwMXJzdCBsaW5lIGEgcG9zaXRpdmUgaW50ZWdlcjogdGhlIG51bWJlciBvZiB0ZXN0IGNhc2VzLCBhdCBtb3N0IDEwMC4gQWZ0ZXIgdGhhdCBwZXIgdGVzdCBjYXNlOjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPm9uZSBsaW5lIHdpdGggdHdvIGludGVnZXJzIHcgYW5kIGggKDIgJmxlOyB3OyBoICZsZTsgNTApOiB0aGUgd2lkdGggYW5kIGhlaWdodCBvZiB0aGUgYnVpbGRpbmcgc2l0ZS48XC9saT5cclxuXHQ8bGk+b25lIGxpbmUgd2l0aCB0aHJlZSBpbnRlZ2VycyBkLCBmIGFuZCBiICgxICZsZTsgZCwgZiwgYiAmbGU7IDEwIDAwMCk6IHRoZSBjb3N0cyBmb3IgZGlnZ2luZyBhIG5ldyBob2xlLCBcdWZiMDFsbGluZyBhbiBleGlzdGluZyBob2xlLCBhbmQgYnVpbGRpbmcgYSBib3VuZGFyeSBlbGVtZW50IGJldHdlZW4gYSBwb29sIGFuZCBncmFzcyBwYXRjaC48XC9saT5cclxuXHQ8bGk+aCBsaW5lcyBvZiB3IGNoYXJhY3RlcnMgZWFjaCwgZGVub3RpbmcgdGhlIGxheW91dCBvZiB0aGUgb3JpZ2luYWwgYnVpbGRpbmcgc2l0ZS48XC9saT5cclxuPFwvdWw+XHJcbiIsIm91dHB1dCI6IjxwPlBlciB0ZXN0IGNhc2U6PFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+b25lIGxpbmUgd2l0aCBhbiBpbnRlZ2VyOiB0aGUgY29zdCBvZiBidWlsZGluZyB0aGUgY2hlYXBlc3QgcG9zc2libGUgcG9vbCBhcmVhIGZyb20gdGhlIG9yaWdpbmFsIHBpZWNlIG9mIGxhbmQuPFwvbGk+XHJcbjxcL3VsPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=

출처

ACM-ICPC > Regionals > Europe > Northwestern European Regional Contest > NWERC 2011 F번