Problem C
Folded Map
Freddy’s garden became so large that he needs a map to keep evidence of which vegetables are planted in what area. He ordered a high-quality map from the International Cartographic Publishing Company (ICPC). Since the map has a large scale, it does not fit onto a single page and it has to be split into several rectangular tiles.
Even with a fixed tile size (determined by a page size) and map scale, the number of tiles may still differ by adjusting the position of the tile grid. Your task is to find the minimal number of tiles necessary to cover the whole region of Freddy’s garden.
![\includegraphics[width=0.6\textwidth ]{texas}](/problems/foldedmap/file/statement/en/img-0001.png)
Let’s have a look at Figure 1. The figure on the left shows 14 map tiles covering a region. By adjusting the grid position a little bit, we may cover the same region with only 10 tiles, without changing their size or orientation.
Note that the tiles must be part of a rectangular grid aligned with the $x$-axis and $y$-axis. That is, they touch each other only with their whole sides and cannot be rotated.
Input
The input contains several test cases. The first line of each test case contains four integer numbers: $A_ r$, $A_ c$, $T_ r$, and $T_ c$. $A_ r$ and $A_ c$ give the input image resolution in pixels ($1 \le A_ x \le 1000$), while $T_ r$ and $T_ c$ is the size of one tile in pixels ($1 \le T_ x \le 100$). The next $A_ r$ lines each contain $A_ c$ characters, each of them being either “X” (the pixel corresponds to a part of the garden to be covered by a tile) or “.” (the corresponding pixel is outside the garden and does not need to be covered). The region pixels form one connected region.
Output
For each test case, print one integer number — the minimal number of tiles necessary to cover all pixels represented by “X”.
| Sample Input 1 | Sample Output 1 |
|---|---|
3 3 2 2 XXX XXX XXX 3 3 2 2 XX. XXX XXX 17 32 5 9 ........XXXXXXXX................ ........XXXXXXXX................ ........XXXXXXXX................ ........XXXXXXXXX............... ........XXXXXXXXXXXXXXX......... ........XXXXXXXXXXXXXXXXXXXX.... ........XXXXXXXXXXXXXXXXXXXXX... XXXXXXXXXXXXXXXXXXXXXXXXXXXXXX.. ..XXXXXXXXXXXXXXXXXXXXXXXXXXXXX. ....XXXXXXXXXXXXXXXXXXXXXXXXXXX. ......XXXXXXXXXXXXXXXXXXXXXXXXX. ........XX..XXXXXXXXXXXXXXXXX... .............XXXXXXXXXXXXXX..... ...............XXXXXXXXX........ ................XXXXXXX......... .................XXXXX.......... ....................XXX......... |
4 3 10 |