НачалоПодразделы
Другие разделы
| 1610. Сложение |
| 1611. Choose the participants |
| 1612. Runeology |
| 1613. Difference |
| 1615. Color sorting |
| 1616. Permutations |
| 1617. Parking |
Дата и время
22/11/2024 10:21:08
1614. Monoliteral polygon
Monoliteral polygon
Задачи на идеюСпециальные способы вычислений
Олимпиадные задачи на английском языке
| 04/07/2011 | Лето 2011 - дорешивание (08E) |
| 13/07/2011 | Лето 2011 - 8 (E) |
Ограничения: время – 5s/10s, память – 64MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод 
Послать решение Blockly Посылки Темы Где Обсудить (0)
Mirko soon realised that number sequences are not the best career choice, and went right back to letter-table 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
lower-right `(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.
Input
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.
Output
In the first and only line of output, print expected number of polygons.
Sample Input 1
3 3 aaa aaa aaa 4 2 0 2 2 0 2 0 0
Sample Output 1
4
Sample Input 2
3 3 aaa aba aaa 4 2 0 2 2 0 2 0 0
Sample Output 2
0
Sample Input 3
5 4 xyyx xyyy xxyy xxxx xxxx 8 1 3 1 2 0 2 0 0 2 0 2 1 3 1 3 3
Sample Output 3
2
