Czech ACM Student Chapter
Czech Technical University in Prague
Charles University in Prague
Technical University of Ostrava
acm
ˇ a
Slovak University of Technology
Pavol Jozef Saf´rik University in Koˇice
s
cz
ˇ
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.
1
1
2
3
4
2
3
4
5
6
7
8
5
6
7
8
9
10
11
12
9
10
13
14
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
