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

문제

2021년, 냅다 ㄷ 만들기는 한국인의 기본 소양이 되었다. 우리는 앞에 놓여있는 $n \times m$ 모눈종이에 냅다 ㄷ을 그리려 한다.

ㄷ 모양은 $k \times k$ 정사각형 7개를 붙인 형태로 정의한다. 다음은 각각 $k=1, k=2$일 때의 ㄷ 모양이다.

ㄷ 모양이 아닌 것의 예는 다음과 같다.

7개의 $k \times k$ 정사각형으로 이루어지지 않음 ㄷ 모양을 뒤집거나 돌릴 수는 없음

모눈종이의 일부 칸에는 이미 검은색이 칠해져 있다. 흰색 칸을 검은색으로 칠하는 데 드는 비용은 $a$, 검은색 칸을 지워서 흰색 칸으로 만드는 데 드는 비용은 $b$다. 검은색 칸들이 ㄷ 모양을 이룰 수 있도록 하기 위해 드는 최소 비용을 구하는 프로그램을 작성하자.

ㄷ 모양의 위치와 크기에는 제한이 없지만, 뒤집거나 돌릴 수는 없으며, 모눈종이를 벗어나도 안 된다. 또한, 모든 검은색 칸은 ㄷ 모양에 포함되어야 하고, ㄷ 모양에 포함되지 않는 칸은 모두 흰색이어야 한다.

입력

첫 번째 줄에 모눈종이의 크기 $n, m$이 주어진다.

두 번째 줄에 칸의 색깔을 바꾸는 데 드는 비용 $a,b$가 주어진다.

다음 $n$개의 줄에 길이 $m$인 문자열이 주어진다. #은 검은색으로 칠해진 칸, .은 흰색 칸을 의미한다.

출력

첫 번째 줄에 ㄷ 모양을 만들 수 있는 최소 비용을 출력한다.

제한

  • $3 \le n,m \le 20$
  • $1 \le a,b \le 1000$

예제 입력 1

3 3
2 5
#.#
.#.
#.#

예제 출력 1

11

예제 입력 2

6 7
10 15
.#####.
.#####.
.#.....
.#.....
.#####.
.#####.

예제 출력 2

60

예제 입력 3

8 8
1000 1
..#..#..
.#..#..#
#..#..#.
..#..#..
.#..#..#
#..#..#.
..#..#..
.#..#..#

예제 출력 3

4018

예제 입력 4

8 8
1 1000
..#..#..
.#..#..#
#..#..#.
..#..#..
.#..#..#
#..#..#.
..#..#..
.#..#..#

예제 출력 4

11018

출처

University > 제주대학교 > 2021 하반기 취업 알고리즘 집중특강 및 해커톤 대회 D번