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.

The input consists of a single test case. The first line
contains two integers, $1 \leq W
\leq 24$ and $1 \leq H
\leq 18$, that designate the width and height of the
mosaic, respectively. Following that are $H$ additional lines, each with
$W$ characters. The
characters `0`, `1`,
`2`, `3`, and `4` designate black squares with the indicated
constraint on the number of neighboring triangles, and the
character ’`*`’ designates a black square
without such a constraint. All remaining locations will be
designated with a ’`.`’ character and must
either be left empty or covered with a single black triangle.
Inputs have been chosen so that they define a valid and unique
mosaic.

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 |