P6504 [COCI 2010/2011 #3] MONO

You are given an $r \times c$ matrix consisting of lowercase letters. Each cell contains one letter. In this setting: - The top-left corner has coordinates $(0,0)$. - The top-right corner has coordinates $(c,0)$. - The bottom-left corner has coordinates $(0,r)$. - The bottom-right corner has coordinates $(c,r)$. **Note that these coordinates refer to grid points, while letters are placed inside cells.** You are given a polygon whose vertices lie on some grid points, and whose edges are all parallel to the sides of the matrix. Please determine, after translating this polygon up, down, left, and right, what is the maximum number of different positions such that all letters inside the polygon are the same.

The first line contains two integers $r, c$, the height and width of the rectangle. The next $r$ lines each contain $c$ letters, describing the matrix. The next line contains an integer $V$, the number of vertices of the polygon. The next $V$ lines each contain two integers $x, y$, representing the coordinates of one vertex of the polygon. The vertices are given in clockwise order.

Output one integer in a single line, representing the number of translated polygon positions whose interior letters are all the same.

#### Constraints - For $40\%$ of the testdata, $r, c, V \le 20$. - For $70\%$ of the testdata, $V \le 20$. - For $100\%$ of the testdata, $1 \le r, c \le 500$, $4 \le V \le 500$, $0 \le x \le c$, $0 \le y \le r$. #### Notes **This problem is translated from [COCI2010-2011](https://hsin.hr/coci/archive/2010_2011/) [CONTEST #3](https://hsin.hr/coci/archive/2010_2011/contest3_tasks.pdf) *T6 MONO***。 Translated by ChatGPT 5