이미지의 에너지
시간 제한2초메모리 제한128 MB
격자의 각 칸을 흑백으로 배정해 셀 비용과 인접 셀 불일치 비용의 합을 최소화하는 문제로, 그래프 최소 컷으로 풀어야 합니다.
문제
회색조 이미지는 n×m개의 칸으로 이루어져 있고, 각 칸의 값은 0 이상 255 이하의 정수이다. 각 칸을 흑색 또는 백색 중 하나로 근사할 때, 근사 이미지의 에너지는 다음 값들의 합으로 정의한다.
- 값이 X인 칸을 흑색으로 근사하면 |X - A|가 더해진다.
- 값이 X인 칸을 백색으로 근사하면 |X - B|가 더해진다.
- 변을 공유하는 두 인접한 칸의 값이 각각 X, Y이고 두 칸을 서로 다른 색으로 근사하면 |X - Y|가 더해진다.
상수 A와 B가 주어졌을 때, 모든 칸의 색을 정해 만들 수 있는 근사 이미지의 최소 에너지를 구하시오.
입력
첫째 줄에 네 정수 n, m, A, B가 주어진다. 1 ≤ n, m ≤ 20이고 0 ≤ A, B ≤ 255이다.
다음 n개의 줄에는 이미지의 각 행을 나타내는 m개의 정수가 주어진다. 각 값은 0 이상 255 이하이다.
출력
가능한 최소 에너지를 출력한다.