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