캠핑장 부지 평탄화

시간 제한1초메모리 제한1024 MB

요약
고도 지도에서 고정된 R×C 작업 계획도를 뺀 값이 창 안의 모든 칸에서 같아지는 위치의 수를 센다.
난이도

보통10점 중 4점

유형
완전 탐색, 구현, 배열
정답자
아직 제출이 없습니다

문제

(주)영일건설은 정적산 일대의 아름다운 경관을 널리 알리고자, 이 지역에 R×CR \times C 크기의 부지를 선정하여 캠핑장을 조성할 계획이다.

캠핑장을 짓기 위해서는, 지반을 고르게 다지는 기초 평탄화 작업이 필요하며, 이를 위해 사전에 정의된 작업 계획도를 활용한다.

작업 계획도는 R×CR \times C 크기의 격자판으로, 각 칸에는 해당 위치에서 얼마만큼 고도를 줄여야 하는지가 기록되어 있다. 즉, 작업 계획도는 캠핑장 부지를 평평하게 만들기 위한 설계도로, 모든 지점의 고도를 줄이는 방향으로만 작업이 이루어진다.

정적산 일대의 지형은 N×MN \times M 크기의 지도로 주어지며, 이는 각 지점의 해발 고도를 담은 격자 형태의 데이터다.

이 지도에서 작업 계획도의 크기와 같은 R×CR \times C 크기의 격자 영역을 선택하여, 작업 계획도와 정확히 겹치도록 한 후, 각 지점에 대해 지도에 적힌 고도에서 작업 계획도에 적힌 값을 빼보았을 때, 해당 격자 영역 내 모든 지점의 고도가 동일해진다면 해당 위치는 평탄화가 가능한 부지로 판단한다. 단, 작업 계획도는 회전하거나 변형할 수 없으며, 주어진 형태 그대로 적용해야 한다. 음수의 고도로도 평탄화가 가능함에 유의한다.

캠핑장 부지는 아직 확정되지 않았기 때문에, 먼저 평탄화가 가능한 후보 부지들을 지도에서 탐색해야 한다.

주어진 지도와 작업 계획도를 바탕으로, 평탄화가 가능한 R×CR \times C 크기의 부지가 총 몇 곳인지 확인해 보자.

입력

첫 번째 줄에 지도의 행의 개수와 열의 개수를 나타내는 두 정수 NN, MM 그리고 작업 계획도의 행의 개수와 열의 개수를 나타내는 RR, CC가 공백으로 구분되어 주어진다. (1≤N,M≤1,000;(1 \leq N, M \leq 1\\,000; 1≤R≤min⁡(9,N);1 \leq R \leq \min(9, N); 1≤C≤min⁡(9,M);1 \leq C \leq \min(9, M); 1≤R×C≤9)1 \leq R \times C \leq 9)

두 번째 줄부터 NN개의 줄에 걸쳐 지도의 고도 정보가 주어진다. 각 줄은 한 행에 해당하며, MM개의 정수가 공백으로 구분되어 주어진다. 이 정수들은 해당 행의 첫 번째 열부터 MM번째 열까지의 해발 고도를 의미하며, 11 이상 99 이하의 정수이다.

그다음 줄부터 RR개의 줄에 걸쳐 작업 계획도 정보가 주어진다. 각 줄은 한 행에 해당하며, CC개의 정수가 공백으로 구분되어 주어진다. 이 정수들은 해당 행의 첫 번째 열부터 CC번째 열까지의 줄여야 하는 고도를 의미하며, 00 이상 99 이하의 정수이다.

출력

평탄화 가능한 후보지 최대 개수를 출력한다.

예제1

  1. 예제 1

    입력
    3 5 2 2
1 2 3 2 4
2 3 4 3 4
3 4 5 4 5
1 2
2 3
    예상 출력
    5