题目描述
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.
输入
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.
样例输入 Copy
100 100
0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
0000000000000000000111100000000000000000000000000000000000000000000000000000000000000000000000000000
0000000000000000011111111111100000000000000000000000000000000000000000000000000000000000000000000000
0000000000000000111111111111111100000000000000000000000000000000000000000000000000000000000000000000
0000000000000001111111111111111110000000000000000000000000000000000000000000000000000000000000000000
0000000000000011111111111111111110000000000000000000000000000000000000000000000000000000000000000000
0000000000000111111111111111111111000000000000000000000000000000000000001111111000000000000000000000
0000000000011111111111111111111111000000000000000000000000000000000000110000000110000000000000000000
0000000000011111101111111111111111100000000000000000000000000000000011000000110001100000000000000000
0000000000111111000011111111111111100000000000000000000000000000000100011100000000010000000000000000
0000000000111111000000011111111111110000000000000000000000000000001001000010011100001000000000000000
0000000000111111100000000011110111110000000000000000000000000000010000011000100010000100000000000000
0000000000111111000000000000000111110000000000000000000000000000010000100101000010000100000000000000
0000000001111110000000000000000111110000000000000000000000000000100001000101011010000010000000000000
0000000001111110000000000000000111110000000000000000000000000000100001011101011010000010000000000000
0000000001111111000000000000000011110000000000000000000000000001000001011101000010000001000000000000
0000000001111100000000000000000011111000000000000000000000000001000000100101000100000001000000000000
0000000001110001110000000111100011111000000000000000000000000001000000011000111000000001000000000000
0000000001110111111000011111110001110000000000000000000000000001000110000010000001100001000000000000
0000000000110000001000000000000001110000000000000000000000000001001000000100100000010001000000000000
0000000000110011110100001111000000110000000000000000000000000001001010001000010001001001000000000000
0000000000110110010100001001100000110000000000000000000000000001000001001000100010000001000000000000
0000000000010011100100000111000000100000000000000000000000000000100001100111000110000010000000000000
0000000000010000001100000000000000100000000000000000000000000000100000110000001100000010000000000000
0000000000010000001100000000000000100000000000000000000000000000010000101111110100000100000000000000
0000000000010000001100000000000000100000000000000000000000000000010000010000001000000100000000000000
0000000000011000001100000000000000100000000000000000000000000000001000001011010000001000000000000000
0000000000011000001100000000000000100000000000000000000000000000000100000111100000010000000000000000
0000000000001100001100000000000000100000000000000000000000000000000011000000000001100000000000000000
0000000000000100001110000000000000100000000000000000000000000000000000110000000110000000000000000000
0000000000000110001111010000000001000000000000000000000000000000000000001111111000000000000000000000
0000000000000110000111100000000001000000000000000000000000000000000000000000000000000000000000000000
0000000000000010000000000000000010000000000000000000000000000000000000000000000000000000000000000000
0000000000000011001110001100000010000000000000000000000000000000000000000000000000000000000000000000
0000000000000011000111111000000110000000000000000000000000000000000000000000000000000000000000000000
0000000000000001100001100000001010000000000000000000000000000000000000000000000000000000000000000000
0000000000000001110000000000010001000000000000000000000000000000000000000000000000000000000000000000
0000000000000000111000000000110011110000000000000000000000000000000000000000000000000000000000000000
0000000000000011111100000001000011111110000000000000000000000000000000000000000000000000000000000000
0000000000001111111110000010000011111111110000000000000000000000000000000000000000000000000000000000
0000000001111111111111111100000011111111110000000000000000000000000000000000000000000000000000000000
0000001111111111111111000000000011111111110000000000000000000000000000000000000000000000000000000000
0000111111111111111111101100000011111111110000000000000000000000000000000000000000000000000000000000
0000111111111111111111111011000111111111110000000000000000000000000000000000000000000000000000000000
0000111111111111111011111110000111111111110000000000000000000000000000000000000000000000000000000000
0000111111111111111000111000000111111111110000000000000000000000000000000000000000000000000000000000
0000111111111111111000110000001111111111110000000000000000000000000000000000000000000000000000000000
0000111111111111111000110000001111111111110000000000000000000000000000000000000000000000000000000000
0000111111111111111101110000001111111111110000000000000000000000000000000000000000000000000000000000
0000111111111111111111111000001111111111110000000000000000000000000000000000000000000000000000000000
0000111111111111111111111000011111111111110000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000001110000000001111100000000001110000000000
0000000000000000000000000000000000000000000000000000000000000111000000011111110000000011110000000000
0000000000000000000000000000000000000000000000000000000000000111100000111111111000000111100000000000
0000000000000000000000000000000000000000000000000000000000000011110000111111111000011111000000000000
0000000000000000000000000000000000000000000000000000000000000001111111111111111111111110000000000000
0000000000000000000000000000000000000000000000000000000000000000111111111111111111111100000000000000
0000000000000000000000000000000000000000000000000000000000000000011111111111111111000000000000000000
0000000000000000000000000000000000000000000000000000000000000001101101111001111100111000000000000000
0000000000000000000000000000000000000000000000000000000000001111111010000000000010000110000000000000
0000000000000000000011111110000000000000000000000000000001110111111000111000111000111001000000000000
0000000000000000001100000001100000000000000000000000000000001111101001000101000100001110100000000000
0000000000000000010000000000010000000000000000000000000000001111111001010101010100100101111000000000
0000000000000000101111001111001000000000000000000000000000111010110000111000111000101010101000000000
0000000000000001000000000000000100000000000000000000000000010101010000000000000000010110101000000000
0000000000000001000110000110000100000000000000000000000000101110111100001000100000111111010100000000
0000000000000010001001001001000010000000000000000000000001010111111000010000010000110101111100000000
0000000000000010010001001000100010000000000000000000000000011011100100100000001000101100110100000000
0000000000000010010101001010100010000000000000000000000000110101111001000000000100011111110100000000
0000000000000010010101001010100010000000000000000000000001000111101101000000000100011101101010000000
0000000000000010010010000100100010000000000000000000000000011011110001000000000100010110111000000000
0000000000000010001100110011000010000000000000000000000000011011100000101101101000010110011000000000
0000000000000110000001001000000011000000000000000000000000110011110000011111111000101110011000000000
0000000000001011000010000100000100100000000000000000000000110110101000000000000000010111010100000000
0000000000001001000001001000000100100000000000000000000000111111110000000000000000010111110000000000
0000000000000101000111111111000100100000000000000000000001011011111000111111100000011011100000000000
0000000000000101111001010010110100100000000000000000000001011011100011001100011100001111100000000000
0000000000000111100000000000101111000000000000000000000001011011000100001100000011001011111000000000
0000000000000010010011111100010010000000000000000000000001101111000100000000000001001011110000000000
0000000000000010100100000010001010000000000000000000000001011101001000000000000000100111110000000000
0000000000000010101000010001010010000000000000000000000001101111101000000000000000100101110000000000
0000000000000010000001000000000110000000000000000000000001001111000100000000000000100110110000000000
0000000000000001110101010101001100000000000000000000000000011101100100000000000000100101101100000000
0000000000000000011000000000110000000000000000000000000000011111000110000000011000100110100000000000
0000000000000000000111111111000000000000000000000000000000011111000001000000011001100101011000000000
0000000000000000000000000000000000000000000000000000000000001111000001111000011110000111101000000000
0000000000000000000000000000000000000000000000000000000000010110110000000111100000001101111000000000
0000000000000000000000000000000000000000000000000000000000010110110100000000000000100111011000000000
0000000000000000000000000000000000000000000000000000000000000111110111011010000010101100111000000000
0000000000000000000000000000000000000000000000000000000000000011010111011010111111010100100000000000
0000000000000000000000000000000000000000000000000000000000000001101010111101110110010010010000000000
0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
样例输出 Copy
2