시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 55 19 13 32.500%

문제

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

수영장 부지는 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+XHVhZDZjXHVjNWVkXHVjNzQ0IFx1YWRmOCBcdWM3OTBcdWNjYjRcdWI4NWMgXHViMTk0XHViNDU4IFx1YzIxOCBcdWM3ODhcdWIyZTQuIFx1Yzc3NCBcdWI1NGMgXHViNGRjXHViMjk0IFx1YmU0NFx1YzZhOVx1Yzc0MCBcdWM1YzZcdWIyZTQuPFwvbGk+XHJcblx0PGxpPlx1Yzc5NFx1YjUxNFx1YzYwMFx1YjM1OCBcdWFkNmNcdWM1ZWRcdWM1ZDAgXHVhZDZjXHViYTRkXHVjNzQ0IFx1ZDMwY1x1YjI5NFx1YjM3MCBcdWI0ZGNcdWIyOTQgXHViZTQ0XHVjNmE5XHVjNzQwIGRcdWM2ZDBcdWM3NzRcdWIyZTQuPFwvbGk+XHJcblx0PGxpPlx1YWQ2Y1x1YmE0ZFx1Yzc3NFx1YzYwMFx1YjM1OCBcdWFkNmNcdWM1ZWRcdWM1ZDAgXHVhZDZjXHViYTRkXHVjNzQ0IFx1YjljOVx1YWNlMCBcdWM3OTRcdWI1MTRcdWI5N2MgXHVjMmVjXHViMjk0XHViMzcwIFx1YjRkY1x1YjI5NCBcdWJlNDRcdWM2YTlcdWM3NDAgZlx1YzZkMFx1Yzc3NFx1YjJlNC48XC9saT5cclxuXHQ8bGk+XHVjMjE4XHVjNjAxXHVjN2E1XHVjNzU4IFx1YWNiZFx1YWNjNFx1YWMwMCBcdWI0MThcdWIyOTQgXHVhYzAxIFx1YmNjMChcdWM3OTRcdWI1MTRcdWM2NDAgXHVhZDZjXHViYTRkIFx1YzBhY1x1Yzc3NClcdWM1ZDBcdWIyOTQgXHViYjNjXHVjNzc0IFx1YzEzOFx1YzljMCBcdWM1NGFcdWFlMzAgXHVjNzA0XHVkNTVjIFx1YWNiZFx1YWNjNCBcdWNjOThcdWI5YWNcdWI5N2MgXHVkNTc0XHVjNTdjIFx1ZDU1Y1x1YjJlNC4gXHVjNzc0IFx1Yzc5MVx1YzVjNVx1Yzc0MCBcdWQ1NWMgXHViY2MwXHViMmY5IGJcdWM2ZDBcdWM3NzQgXHViNGUwXHViMmU0LjxcL2xpPlxyXG5cdDxsaT5cdWMyMThcdWM2MDFcdWM3YTUgXHViZDgwXHVjOWMwXHVjNzU4IFx1YWMwMFx1YzdhNSBcdWJjMTRcdWFlNjUgXHVkNTg5XHVhY2ZjIFx1YzVmNFx1Yzc0MCBcdWM3OTRcdWI1MTRcdWM3NzRcdWM1YjRcdWM1N2MgXHVkNTVjXHViMmU0LjxcL2xpPlxyXG48XC91bD5cclxuXHJcbjxwPlx1ZDYwNFx1YzdhYyBcdWMyMThcdWM2MDFcdWM3YTUgXHViZDgwXHVjOWMwXHVjNzU4IFx1YjU0NSZuYnNwO1x1YzgxNVx1YmNmNFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM4NGNcdWM3NDQgXHViNTRjLCBcdWMyMThcdWM2MDFcdWM3YTVcdWM3NDQgXHViOWNjXHViNGRjXHViMjk0XHViMzcwIFx1YWMwMFx1YzdhNSBcdWMyZmMgXHViZTQ0XHVjNmE5XHVjNzQ0IFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNzU4IFx1YWMxY1x1YzIxOFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM3NTggXHVhYzFjXHVjMjE4XHViMjk0IDEwMFx1YWMxY1x1Yjk3YyBcdWIxMThcdWM5YzAgXHVjNTRhXHViMjk0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yzc1OCBcdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0Jm5ic3A7XHVjMjE4XHVjNjAxXHVjN2E1IFx1YmQ4MFx1YzljMFx1Yzc1OCBcdWQwNmNcdWFlMzAmbmJzcDt3XHVjNjQwIGhcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoMiAmbGU7IHcsIGggJmxlOyA1MCkgXHViMmU0XHVjNzRjIFx1YzkwNFx1YzVkMFx1YjI5NCBkLCBmLCBiXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKDEgJmxlOyBkLCBmLCBiICZsZTsgMTAsMDAwKSBcdWIyZTRcdWM3NGMgaFx1YWMxYyBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVjMjE4XHVjNjAxXHVjN2E1XHVjNzQ0IFx1YjljY1x1YjRlNCBcdWJkODBcdWM5YzBcdWM3NTggXHVjODE1XHViY2Y0XHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YzVkMCBcdWIzMDBcdWQ1NzRcdWMxMWMsIFx1YzIxOFx1YzYwMVx1YzdhNVx1Yzc0NCBcdWI5Y2NcdWI0ZGNcdWIyOTRcdWIzNzAgXHViNGRjXHViMjk0IFx1YmU0NFx1YzZhOVx1Yzc1OCBcdWNkNWNcdWMxOGNcdWFjMTJcdWM3NDQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LiZuYnNwOzxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjM2NTYiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJQb29sIGNvbnN0cnVjdGlvbiIsImRlc2NyaXB0aW9uIjoiPHA+WW91IGFyZSB3b3JraW5nIGZvciB0aGUgSW50ZXJuYXRpb25hbCBDb21wYW55IGZvciBQb29sIENvbnN0cnVjdGlvbiwgYSBjb25zdHJ1Y3Rpb24gY29tcGFueSB3aGljaCBzcGVjaWFsaXplcyBpbiBidWlsZGluZyBzd2ltbWluZyBwb29scy4gQSBuZXcgY2xpZW50IHdhbnRzIHRvIGJ1aWxkIHNldmVyYWwgbmV3IHBvb2wgYXJlYXMuPFwvcD5cclxuXHJcbjxwPkEgcG9vbCBhcmVhIGlzIGEgcmVjdGFuZ3VsYXIgZ3JpZCBvZiB3ICZ0aW1lczsmbmJzcDtoIHNxdWFyZSBwYXRjaGVzLCBjb25zaXN0aW5nIG9mIHplcm8gb3IgbW9yZSAocG9zc2libHkgZGlzY29ubmVjdGVkKSBwb29scy4gQSBwb29sIGNvbnNpc3RzIG9mIG9uZSBvciBtdWx0aXBsZSBjb25uZWN0ZWQgaG9sZSBwYXRjaGVzLCB3aGljaCB3aWxsIGxhdGVyIGJlIFx1ZmIwMWxsZWQgd2l0aCB3YXRlci4gSW4gdGhlIGJlZ2lubmluZywgeW91IHN0YXJ0IHdpdGggYSBwaWVjZSBvZiBsYW5kIHdoZXJlIGVhY2ggcGF0Y2ggaXMgZWl0aGVyIGEgaG9sZSBpbiB0aGUgZ3JvdW5kICgmcnNxdW87LiZyc3F1bzspIG9yIFx1ZmIwMmF0IGdyYXNzICgmcnNxdW87IyZyc3F1bzspLiBJbiBvcmRlciB0byB0cmFuc2Zvcm0gdGhpcyBsYW5kIGludG8gYSBwb29sIGFyZWEsIHlvdSBtdXN0IGFkaGVyZSB0byB0aGUgZm9sbG93aW5nOjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPllvdSBjYW4gbGVhdmUgYSBwYXRjaCBhcyBpdCBpcy4gVGhpcyBjb3N0cyBub3RoaW5nLjxcL2xpPlxyXG5cdDxsaT5JZiB0aGUgcGF0Y2ggaXMgZ3Jhc3MgaW4gdGhlIGJlZ2lubmluZywgeW91IGNhbiBkaWcgYSBob2xlIHRoZXJlLiBUaGlzIGNvc3RzIGQgRVVSLjxcL2xpPlxyXG5cdDxsaT5JZiB0aGUgcGF0Y2ggaXMgYSBob2xlIGluIHRoZSBiZWdpbm5pbmcsIHlvdSBjYW4gXHVmYjAxbGwgdGhlIGhvbGUgYW5kIHB1dCBncmFzcyBvbiB0b3AuIFRoaXMgY29zdHMgZiBFVVIuPFwvbGk+XHJcblx0PGxpPllvdSBtdXN0IHBsYWNlIHNwZWNpYWwgYm91bmRhcnkgZWxlbWVudHMgYWxvbmcgZWFjaCBlZGdlIHJ1bm5pbmcgYmV0d2VlbiBhIFx1ZmIwMW5hbCBncmFzcyBwYXRjaCBhbmQgYSBcdWZiMDFuYWwgaG9sZSBwYXRjaCwgdG8gZW5zdXJlIHRoYXQgd2F0ZXIgZG9lcyBub3QgbGVhayBmcm9tIHRoZSBwb29sLiBUaGlzIGNvc3RzIGIgRVVSIHBlciBib3VuZGFyeSBlbGVtZW50LjxcL2xpPlxyXG5cdDxsaT5UaGUgb3V0ZXJtb3N0IHJvd3MgYW5kIGNvbHVtbnMgb2YgdGhlIHBvb2wgYXJlYSBtdXN0IGFsd2F5cyBiZSBncmFzcy48XC9saT5cclxuPFwvdWw+XHJcblxyXG48cD5Zb3UgYXJlIGdpdmVuIHRoZSB0YXNrIG9mIGNhbGN1bGF0aW5nIHRoZSBjb3N0IG9mIHRoZSBjaGVhcGVzdCBwb3NzaWJsZSBwb29sIGFyZWEgZ2l2ZW4gdGhlIGxheW91dCBvZiB0aGUgZXhpc3RpbmcgcGllY2Ugb2YgbGFuZC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPk9uIHRoZSBcdWZiMDFyc3QgbGluZSBhIHBvc2l0aXZlIGludGVnZXI6IHRoZSBudW1iZXIgb2YgdGVzdCBjYXNlcywgYXQgbW9zdCAxMDAuIEFmdGVyIHRoYXQgcGVyIHRlc3QgY2FzZTo8XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT5vbmUgbGluZSB3aXRoIHR3byBpbnRlZ2VycyB3IGFuZCBoICgyICZsZTsgdzsgaCAmbGU7IDUwKTogdGhlIHdpZHRoIGFuZCBoZWlnaHQgb2YgdGhlIGJ1aWxkaW5nIHNpdGUuPFwvbGk+XHJcblx0PGxpPm9uZSBsaW5lIHdpdGggdGhyZWUgaW50ZWdlcnMgZCwgZiBhbmQgYiAoMSAmbGU7IGQsIGYsIGIgJmxlOyAxMCAwMDApOiB0aGUgY29zdHMgZm9yIGRpZ2dpbmcgYSBuZXcgaG9sZSwgXHVmYjAxbGxpbmcgYW4gZXhpc3RpbmcgaG9sZSwgYW5kIGJ1aWxkaW5nIGEgYm91bmRhcnkgZWxlbWVudCBiZXR3ZWVuIGEgcG9vbCBhbmQgZ3Jhc3MgcGF0Y2guPFwvbGk+XHJcblx0PGxpPmggbGluZXMgb2YgdyBjaGFyYWN0ZXJzIGVhY2gsIGRlbm90aW5nIHRoZSBsYXlvdXQgb2YgdGhlIG9yaWdpbmFsIGJ1aWxkaW5nIHNpdGUuPFwvbGk+XHJcbjxcL3VsPlxyXG4iLCJvdXRwdXQiOiI8cD5QZXIgdGVzdCBjYXNlOjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPm9uZSBsaW5lIHdpdGggYW4gaW50ZWdlcjogdGhlIGNvc3Qgb2YgYnVpbGRpbmcgdGhlIGNoZWFwZXN0IHBvc3NpYmxlIHBvb2wgYXJlYSBmcm9tIHRoZSBvcmlnaW5hbCBwaWVjZSBvZiBsYW5kLjxcL2xpPlxyXG48XC91bD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d

출처

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