Czech ACM Student Chapter

Czech Technical University in Prague

Charles University in Prague

Technical University of Ostrava

ˇ a

Slovak University of Technology

Pavol Jozef Saf´rik University in Koˇice

s

ˇ

University of Zilina

Masaryk University

Matej Bel University in Bansk´ Bystrica

a

University of West Bohemia

CTU Open Contest 2013

Folded Map

fm.c, fm.cpp, Fm.java

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.

Two of many possible ways of tiling Texas-shaped region

Let's have a look at an example. 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 Specification

The input contains several test cases. The first line of each test case contains four integer

numbers: Ar , Ac, Tr , and Tc. Ar and Ac give the input image resolution in pixels (1 ≤ Ax ≤

1000), while Tr and Tc is the size of one tile in pixels (1 ≤ Tx ≤ 100). The next Ar lines each

contain Ac 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 Specification

For each test case, print one integer number -- the minimal number of tiles necessary to cover

all pixels represented by "X".

Sample Input

3322

XXX

XXX

XXX

3322

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.........

Output for Sample Input

4

3

10