cho.sh

이미지 퀼팅 (작은 입력)

H행 W열 회색조 이미지 두 장이 주어질 때, 각 행에서 한 픽셀씩 고르되 인접한 행의 열 차이가 1 이하인 연결된 이음선을 택해 제곱 차이 합의 최솟값을 구한다.

보통5동적 계획법구현면접 대비아직 제출이 없습니다시간 제한1초메모리 제한512 MB

문제

이미지 퀼팅(image quilting)은 패턴 이미지 하나를 여러 개 이어 붙여 큰 이미지를 만드는 기법이다. 이미지를 그냥 나란히 붙이면 자연스러운 결과가 나오지 않는다. 맞닿는 두 이미지의 가장자리가 서로 많이 다를 수 있기 때문이다.

왼쪽부터 원본 이미지, 단순히 이어 붙인 이미지, 최적화해서 이어 붙인 이미지다.

세 번째 그림처럼 더 자연스러운 결과를 얻으려고 아래 방법을 쓴다. 이 문제에서는 높이가 같은 흑백 이미지 두 개를 좌우로 합치는 경우만 다룬다.

두 이미지를 포개어 자연스러운 경계를 고르는 과정이다.

  • 이어 붙일 두 이미지를 B1과 B2라 하자. B1이 왼쪽, B2가 오른쪽이다.
  • 두 이미지의 가장자리를 조금 포갠다.
  • 포개진 영역에서 B1과 B2의 차이가 가장 작아지도록 경계선을 정한다. 경계선과 그 오른쪽은 B2의 픽셀로 덮어써서 새 이미지를 만든다.
    • 경계선은 포개진 영역의 각 행마다 픽셀을 하나씩 골라 만든다.
    • 어떤 행에서 고른 픽셀은 바로 위 행이나 바로 아래 행에서 고른 픽셀과 열 번호가 1을 넘게 차이 날 수 없다. 즉 이웃한 두 행의 선택은 좌우로 1칸 이내에서만 어긋난다.
    • 각 행에서 고른 픽셀의 왼쪽은 B1의 색을 그대로 쓰고, 고른 픽셀과 그 오른쪽은 B2의 색으로 덮어쓴다.

포개진 5행 10열 영역에서 고른 경계선의 예다.

가능한 경계선이 아주 많으므로 그중 두 이미지를 가장 자연스럽게 잇는 것을 골라야 한다. 경계선의 부자연스러운 정도는 경계선 위의 각 픽셀 위치에서 B1의 색상 값과 B2의 색상 값의 차를 제곱해 모두 더한 값이다. 가장 자연스러운 경계선은 이 값이 가장 작은 경계선이다.

포개진 영역의 B1 이미지와 B2 이미지, 그리고 최적 경계선이다.

이 문제는 흑백 영상만 다루므로 각 픽셀의 색상 값은 0 이상 255 이하의 정수다. 위 예에서는 세 번째 그림처럼 경계선을 고르면 최적이고, 이때 부자연스러운 정도는 다음과 같다.

E=(79−62)2+(10−16)2+(130−120)2+(235−240)2=450E = (79-62)^2 + (10-16)^2 + (130-120)^2 + (235-240)^2 = 450

포개질 영역의 색상 값이 주어질 때, 고를 수 있는 경계선의 부자연스러운 정도 중 최솟값을 구하는 프로그램을 작성하시오.

입력

첫 줄에 포개진 영역의 높이 HH와 너비 WW가 공백으로 구분되어 주어진다. (1≤H≤101 \le H \le 10, 1≤W≤101 \le W \le 10) HH는 행의 수, WW는 열의 수다. 포개질 영역의 색상 값만 주어지며, 두 이미지 모두 HH행 WW열이다.

다음 HH개 줄에는 B1 이미지의 색상 값이 주어진다. 각 줄은 영상의 한 행이고, 픽셀 WW개의 색상 값이 0 이상 255 이하의 정수로 공백으로 구분되어 주어진다. 입력의 행과 열 순서는 실제 영상의 행과 열 순서와 같다. 그 다음 HH개 줄에는 같은 형식으로 B2 이미지의 색상 값이 주어진다.

출력

고를 수 있는 경계선의 부자연스러운 정도 중 최솟값을 한 줄에 출력한다.