Problem A
Mosaic
In this problem, we consider a special class of tile mosaics, as exemplified in Figure 1. Each such mosaic is built on a rectangular grid with a white background. Within each cell of the grid is either a square black tile, a triangular black tile in one of the four orientations shown in Figure 2, or nothing, in which case the grid cell remains white. Furthermore, each mosaic is designed so that any shape that remains white is rectangular (possibly rotated).
To install such a mosaic, an artist starts by placing all the black squares. Remaining black triangles will later be added by assistants in order to complete the pattern. To ensure that the assistants complete the mosaic as envisioned, the artist marks some of the black tiles with a numeric label that indicates the number of black triangles that share an edge with that square. (Black tiles without a label may have any number of neighboring triangles.) The artists provides enough labels to ensure a unique design.
For example, Figure 3 shows a starting configuration that uniquely defines the mosaic shown in Figure 1. Given such a starting configuration, you are to determine the number of triangles needed to complete the mosaic.
Input
The input consists of a single test case. The first line
contains two integers,
Output
Display the number of triangles used in the mosaic.
Sample Input 1 | Sample Output 1 |
---|---|
9 5 ....0*... ....2.... ......... 2.......1 .2..3.... |
20 |
Sample Input 2 | Sample Output 2 |
---|---|
5 5 2...* ..... ..... ..... *...0 |
14 |
Sample Input 3 | Sample Output 3 |
---|---|
18 10 *1....*2.....**2.. 2.............3... ...4.............. ....4..*.....*.... 2*...*3.....3..... .....*.....**...3* ....3.....3..3.... ..............4... ...1.............0 ..1*2.....2*....1* |
92 |