11398번 - 흑백 이미지 찾기

흑백 이미지에는 색이 없다. 따라서 흑백 이미지를 표현할 때에는, 각 픽셀마다 그 픽셀의 밝기를 나타내는 수치 하나만 기록한다. 이 문제에서는 0 이상 65,535 이하의 정수로 한 픽셀의 밝기를 나타낼 수 있다고 하자.

H × W 크기의 흑백 사진 I는 H × W개의 픽셀들이 H행 W열로 배열된 형태라고 생각하고, i (1 ≤ i ≤ H)행 j (1 ≤ j ≤ W)열에 있는 픽셀의 밝기를 I[i, j]로 표현하자.

경근이는 N × M 크기의 흑백 이미지 A와 R × C 크기의 흑백 이미지 B를 가지고 있다. 이때 N ≥ R, M ≥ C이다. (A가 B보다 가로/세로 길이가 모두 더 길다) 경근이는 A가 B를 표절했다고 생각하고, A에서 B와 비슷한 부분이 몇 개나 되는지 찾고자 한다.

그 방법은 다음과 같다. 우선 흑백 이미지 A에서 R × C 크기의 픽셀로 구성된 직사각형을 하나 선택한다. 이 직사각형은 좌측 상단 꼭짓점에 있는 픽셀의 위치 (x, y) (1 ≤ x ≤ N - R + 1, 1 ≤ y ≤ M - C + 1)에 의해 결정된다.

예를 들어 위 흑백 이미지를 A라고 하자. A에서 4 × 6 크기의 직사각형을 하나 선택했다고 하면 이 직사각형은 좌측 상단 꼭짓점인 (4, 4)에 의해 결정된다. (만약 좌측 상단 꼭짓점을 움직이면, 크기가 고정되어 있으므로, 직사각형도 같이 움직일 것) 이 직사각형의 우측 하단 꼭짓점은 (7, 9)인데, 이는 (4 + 4 - 1, 4 + 6 - 1)과 같다.

이제 이 직사각형과 사진 B가 비슷한지를 판단하는데, 그 기준은 다음과 같다.

어떤 실수 p와 q가 모든 1 ≤ i ≤ R, 1 ≤ j ≤ C에 대해 p·A[x + i - 1, y + j - 1] + q = B[i, j]를 만족시키면, A에서 선택한 직사각형과 사진 B는 비슷하다.

이 판단 기준을 A에 있는 모든 R × C 크기의 직사각형에 대해 적용하여, B와 비슷한 직사각형의 개수를 세면 된다. 다시 말해 1 ≤ x ≤ N - R + 1, 1 ≤ y ≤ M - C + 1를 만족하는 모든 (x, y)에 대해 위 판단 기준을 적용한 후, 비슷하다고 판단되는 (x, y) 쌍의 수를 세면 된다. 참고로 크기가 같은 두 직사각형이 다르다는 것은 좌측 상단 꼭짓점의 좌표가 서로 다르다는 것으로, 직사각형 내부 픽셀의 밝기와는 관계가 없다.

여러분은 경근이를 도와 A에서 B와 비슷한 부분이 몇 개인지 구하는 프로그램을 작성해야 한다.

첫 번째 줄에 흑백 이미지 A의 행의 수 N, 열의 수 M (1 ≤ N, M ≤ 10³)이 공백을 사이로 두고 주어진다.

다음 N개의 줄에는 A의 픽셀들에 대한 정보가 주어진다. 이 중 i (1 ≤ i ≤ N)번째 줄에는 M개의 정수 A[i, 1], A[i, 2], ..., A[i, M - 1], A[i, M]이 공백을 사이로 두고 주어진다. 즉 i번째 줄에서 j번째로 주어지는 정수는 A의 i행 j열에 있는 픽셀의 밝기를 의미한다.

그 다음 줄에 흑백 이미지 B의 행의 수 R, 열의 수 C (1 ≤ R ≤ N, 1 ≤ C ≤ M)이 공백을 사이로 두고 주어진다.

다음 N개의 줄에는 B의 픽셀들에 대한 정보가 주어진다. 이 중 i (1 ≤ i ≤ R)번째 줄에는 C개의 정수 B[i, 1], B[i, 2], ..., B[i, C - 1], B[i, C]이 공백을 사이로 두고 주어진다. 즉 i번째 줄에서 j번째로 주어지는 정수는 B의 i행 j열에 있는 픽셀의 밝기를 의미한다.

주어지는 모든 픽셀 밝기는 0 이상 65,535 이하의 정수임이 보장된다.

A에서 B와 비슷한 부분의 개수를 출력한다.

두 번째 예제의 경우 p = 0, q = 77이면 모든 부분이 비슷하다고 판별된다.