시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 512 MB 87 41 38 52.055%

문제

이미지 퀼팅(Image Quilting)이란, 하나의 패턴 이미지를 여러 개 이어붙여서 큰 이미지를 만들어내는 것을 말한다. 하지만 단순히 이미지를 나란히 이어붙이는 것만으로는 자연스러운 이미지를 얻을 수 없다. 이어 붙여질 이미지의 경계가 서로 많이 다를 수 있기 때문이다.

<왼쪽부터 원본 이미지, 단순히 이어붙인 이미지, 최적화하여 이어붙인 이미지>

위와 같은 문제를 해결하고 위의 3번째 이미지같이 더욱 자연스러운 이미지를 얻기 위하여 아래와 같은 방법을 사용한다. 이 문제에서는 편의상 높이가 같은 두 흑백 이미지를 좌우로 합치는 것만 고려한다.

<두 이미지를 포개어 자연스러운 경계를 선택하는 과정>

  • 이어붙일 두 이미지를 B1과 B2라고 하자. (B1은 왼쪽, B2는 오른쪽)
  • 두 이미지의 경계를 조금 포갠다. 포갠 영역의 너비는 최소 2픽셀이다.
  • 포개어진 영역에서 B2와 B1 이미지의 차이가 최소가 되도록 경계선을 결정한다. 그리고 경계선과 그 오른쪽 부분을 B1 이미지에 B2 이미지를 덮어써서 새로운 이미지를 생성한다.
    • 경계선은 포개진 영역의 한 행마다 하나의 픽셀을 선택하여 생성한다.
    • 경계선의 각 행에 선택된 픽셀은 바로 위 혹은 아래 행에서 선택된 픽셀과 두 칸 이상 떨어질 수 없다. 한마디로 한 경계선 픽셀은 자신의 바로 아래 혹은 위의 행의 경계선 픽셀과 좌우로 +1, 0, 1칸 차이가 나는 것만 허용된다.
    • 각 행은 경계선으로 선택된 픽셀을 기준으로 그 왼쪽은 B1 이미지의 픽셀을 그대로 사용하고, 그 픽셀과 이후 오른쪽 픽셀들은 B2 이미지의 픽셀로 덮어쓰게 된다.

<포개어진 5X10 영역에서 선택된 경계선 예시>

실제로 포개어진 영역에 존재할 수 있는 경계선은 경우의 수가 많기 때문에 이 중에 가장 자연스럽게 두 이미지를 이어붙일 수 있는 경계를 선택하여야 한다.  경계선의 부자연스러움 정도는 경계선상의 존재하는 각 픽셀 위치에서의 B1 이미지의 픽셀과 B2 이미지의 픽셀의 색상 값의 차를 제곱하여 모두 더한 값으로 정의할 수 있다. 물론 가장 자연스러운 경계선은 이 중 부자연스러운 정도가 가장 낮은 경계선을 의미한다.

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

이 문제에서는 흑백 영상만을 다루므로 각 픽셀은 0~255의 정수 형태의 색상 값으로 표현할 수 있다. 위의 예시에서 두 이미지는 세 번째 그림과 같이 경계선을 선택하면 최적이라고 할 수 있으며 이때의 부자연스러움 정도는 아래와 같이 계산할 수 있다.

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

두 이미지의 포개어질 영역의 색상값들이 주어질 때, 선택할 수 있는 최적의 경계선이 가지는 최소의 부자연스러움 정도를 계산하여 출력하는 프로그램을 작성하시오.

입력

첫 줄에는 포개어진 두 이미지의 높이 H (1 ≤ H ≤ 10) 와 포개어진 영역의 너비 W (1 ≤ W ≤ 10) 가 공백으로 구분된 두 자연수로 주어진다. H는 이미지의 행의 수, W는 포개어진 영역의 열의 수를 나타내는 자연수이다. 이 문제는 포개어질 영역의 색상 값만 주어짐에 유의한다. 입력으로 주어지는 두 이미지는 모두 H행 W열이다.

그 후 H줄에 걸쳐서 B1 이미지의 색상값이 주어진다. 각 줄은 영상의 행이며 W개의 픽셀의 색상 값이 0~255 범위의 자연수로 주어진다. 입력으로 주어지는 행/열의 순서와 실제 영상의 행/열의 순서는 일치한다. 그 후 H줄에 걸쳐서 B2 이미지의 색상값이 주어진다. 입력 형식은 위의 B1 이미지와 같다.

출력

두 이미지에서 선택할 수 있는 경계선이 가지는 최소의 부자연스러운 정도를 한 줄에 출력한다.

예제 입력 1

4 3
0 79 240
10 110 230
9 130 213
30 70 235
50 62 237
16 58 99
25 120 170
90 120 240

예제 출력 1

450

채점

  • 예제는 채점하지 않는다.