The Queen of Aces has recently prohibited sending smiling faces via Wondernet. She is anxious, however, that despite the risk of being beheaded, some inhabitants of Wonderland might try to ignore this new law. She is especially suspicious about Alice, so she ordered the secret police to intercept all of Alice's e-mails and search for smiling faces. The police have done a good job and now they have a large bitmap with all faces Alice has ever sent. The only thing they need to find out is how many times Alice should be beheaded.
You are given a matrix of 0's and 1's containing several faces. Determine the number of smiling ones.
A face consists of a number of face elements (FE): a face boundary, two eyes, a nose, a mouth and a number of miscellaneous elements (eyebrows, etc). Each FE is a contiguous area of 1's (using 8-neighborhood). The face always contains a face boundary, two eyes and a mouth. All other FE's are optional.
The face boundary is an FE containing all other FE's. Each face has exactly one face boundary (FB). FB surrounds (possibly more) 4-neighborhood areas of 0's, and all other FE's constituting this face are located within these areas.
Eyes always surround an area of 0's (this area may contain other FE's). The mouth may or may not surround an area of 0's, but no other FE surrounds an area of 0's.
The mouth is always below eyes (i.e. the bottommost 1 of the mouth is always below the bottommost 1 of any eye). The mouth has the greatest left-to-right length among all FE's below eyes excluding the boundary.
A face is smiling if the topmost 1 of the mouth is at the same the leftmost 1 or the rightmost 1 of the mouth.
 |
 |
|
| A smiling face | A non-smiling face |
The first line contains two integers M, N representing the height and the width of the matrix. This is followed by M lines, each containing a string of length N of zeroes and ones.
No two faces overlap or touch each other. All objects in the matrix are valid faces. No two FE's overlap or touch. The border of the matrix consists of 0's only.
A single integer containing the number of smiling faces.