프로그램 명: coci_mono
제한시간: 5 초
미르코는 숫자 시퀀스가 최선의 직업선택이 아니라는 것을 알게 되었다.그리고 글자 판 사업에 곧장 돌아갔다.
미르코의 판은 R 행 및 C 열에 소문자를 가지고 있다. 판의 각 셀은 동일한 크기의 사각형이다. 판의 왼쪽 위 모서리의 좌표는 (0, 0), 오른쪽 위는(C, 0),왼쪽 아래는(0, R), 그리고 오른쪽 아래는(C, R)이다.
우리는 아래의 것을 따르면 판이 같은 문자로 되있을 때를 포함하여 다각형이라고 한다.
- .그것의 꼭짓점들은 각각의 사각형의 꼭짓점으로 되있다.
- 그것의 가장자리는 축과 평행하다.
- .다각형 내부는 모든 글자가 같습니다.
처음 두 조건 이 참인 간단한 다각형 (3번째의 조건이 이루어지지 않을 수 있다.)가 주어졌습니다.
미르코는 한번 위,아래,왼쪽 또는 오른쪽으로 움직이거나 또는 이들을 조합해 만들어진 같은 문자로 되있는 다각형의 개수가 궁금해졌다.(그러나 돌리면 않된다.)
입력
- 입력의 첫 줄은 행의 개수 R 과 열의 개수 C가 두 공백을 두고 주어진다(1 ≤ R,C ≤ 500).
- 다음 R줄에는 C개의 소문자가 주어진다. 이것은 미르코의 테이블이다.
- 그 다음 줄에는 주어진 다각형의 꼭지점의 개수인 정수 V가 주어진다(4 ≤ V ≤ 500).
- 다음 V줄에는 다각형의 꼭지점의 좌표인 정수 X,Y가 주어진다(0 ≤ X ≤ C, 0 ≤ Y ≤ R).이것은 시계방향 순서로 주어진다.
주어진 다각형은 위의 조건 1과 2를 충족한다.
출력
첫째 줄에 다각형의 수를 출력한다.
Mirko soon realised that number sequences are not the best career choice, and went right back to lettertable business.
Mirko’s table has R rows and C columns and consists of lowercase letters.
Each cell of the table is a square of equal size. We assign coordinates to vertices of those squares, so
that upper-left corner of the table has coordinates (0, 0), upper-right (C,0), lower-left (0, R), and lowerright
(C, R).
We say that polygon within the table is monoliteral if the following holds:
- its vertices are from the described set of cell-square vertices,
- its edges are parallel to coordinate axes,
- all letters inside the polygon are equal.
A simple polygon for which first two conditions are true (third one may or may not be true) is given.
Mirko would like to know the number of monoliteral polygons that can be obtained by moving the
given one up, down, left, or right or any combination thereof, but not rotating.
입력
-
The first line of input contains two space seperated integers R and C (1 ≤ R, C ≤ 500).
- Each of the next R lines contains exactly C lowercase letters, this is Mirko’s table.
- The following line contains integer V (4 ≤ V ≤ 500), number of vertices of given polygon.
- Each of the next V lines contains two integers X, Y (0 ≤ X ≤ C, 0 ≤ Y ≤ R). These are the coordinates
of the vertices of the given polygon. Vertices are given in clockwise order.
The given polygon will satisfy conditions 1 and 2 from above.
출력
In the first and only line of output, print expected number of polygons.
입출력 예
입력
3 3
aaa
aaa
aaa
4
2 0
2 2
0 2
0 0
출력
4
입력
3 3
aaa
aba
aaa
4
2 0
2 2
0 2
0 0
출력
0
입력
5 4
xyyx
xyyy
xxyy
xxxx
xxxx
8
1 3
1 2
0 2
0 0
2 0
2 1
3 1
3 3
출력
2
출처: coci 2010
번역: po10003
[질/답]
[제출 현황]
[푼 후(0)]