한 글자 다각형
시간 제한2초메모리 제한128 MB
주어진 직사각형 격자 다각형을 정수만큼 평행이동했을 때 표 안에 완전히 들어가고 내부 셀이 모두 같은 문자인 위치의 개수를 구합니다.
문제
R행 C열의 표가 주어진다. 각 칸에는 알파벳 소문자 하나가 적혀 있고, 모든 칸은 같은 크기의 정사각형이다.
표의 꼭짓점에는 좌표가 붙어 있다. 표의 왼쪽 위 꼭짓점은 (0, 0), 오른쪽 위 꼭짓점은 (C, 0), 왼쪽 아래 꼭짓점은 (0, R), 오른쪽 아래 꼭짓점은 (C, R)이다.
표 안에 있는 다각형이 다음 조건을 만족하면 한 글자 다각형이라고 부른다.
- 모든 꼭짓점이 위에서 정의한 칸 꼭짓점 중 하나이다.
- 모든 변이 좌표축과 평행하다.
- 다각형 내부에 포함된 모든 칸의 문자가 서로 같다.
조건 1과 2를 만족하는 단순 다각형 하나가 주어진다. 이 다각형을 회전하지 않고 위, 아래, 왼쪽, 오른쪽으로 정수 거리만큼 평행이동할 수 있다. 이동한 다각형이 표 안에 완전히 들어가며 한 글자 다각형이 되는 서로 다른 위치의 개수를 구하라.
입력
첫째 줄에 두 정수 R과 C가 공백으로 구분되어 주어진다. (1 <= R, C <= 500)
다음 R개 줄에는 길이가 C인 알파벳 소문자 문자열이 하나씩 주어진다. 이는 표의 각 행을 나타낸다.
다음 줄에는 주어진 다각형의 꼭짓점 수 V가 주어진다. (4 <= V <= 500)
다음 V개 줄에는 꼭짓점의 좌표 X, Y가 순서대로 주어진다. (0 <= X <= C, 0 <= Y <= R)
꼭짓점은 시계 방향으로 주어진다. 주어진 다각형은 문제에서 정의한 조건 1과 2를 만족한다.
출력
첫째 줄에 조건을 만족하는 다각형 위치의 개수를 출력한다.