[IPSC2001]笑脸

成绩 0 开启时间 2013年02月21日 星期四 18:02
折扣 0.8 折扣时间 2013年02月28日 星期四 18:02
允许迟交 关闭时间 2013年02月28日 星期四 18:02
输入文件 xl.in 输出文件 xl.out
问题描述   
    Ace 女王最近颁布了一条新法律,禁止在 Wondernet 上发送笑脸。但是女王担心人们还是会冒着被砍头的危险对这条法律置之不理,尤其是 Alice 。女王派警察秘密截获了 Alice 的所有 E-mail 后,叫他们帮忙数数这些 E-mail 里有多少个笑脸,即 Alice 应该被砍头多少次。
    一张脸包含一些元素( Face Element, FE ):两只眼睛,一个鼻子,一张嘴巴和一些诸如眉毛等的其他东西。一个 FE 是一片八连的 “1” 。每张脸至少包含一个封闭的脸边界,两只眼睛和一张嘴,其他 FE 都是可以省略的。
    脸边界把其他 FE 包围在里面,而两只眼睛各包围一个由 0 组成的四连区域(这个区域可以包含其他 FE )。嘴可以包围一个由 0 组成的四连区域,也可以不包围,但是其他 FE 都不能包围这样的区域。嘴总在眼睛的下面(即:嘴最下方的 1 在眼睛最下方的 1 的下面),而在所有 FE 中,嘴是除了边界之外左 - 右跨度最大的一个。

    如果一张嘴最上方的 1 同时也是嘴的最左边或者最右边的 1 ,我们就说这是张笑脸。给出 Alice 那封包含很多脸的 E- mail ,请数一数里面包含了多少笑脸。如图所示,左边是笑脸,右边是非笑脸。

【输入格式】
  输入文件第一行有一个整数n,下面有n行,每行有n个字符"0"或"1",表示Alice 那封包含很多脸的 E- mail.
【输出格式】
 输出文件也只有一行,有一个整数m,表示笑脸的个数.
【输入输出样例】
输入文件名: xl.in
25
0000000001111111000000000
0000000110000000110000000
0000011000000110001100000
0000100011100000000010000
0001001000010011100001000
0010000011000100010000100
0010000100101000010000100
0100001000101011010000010
0100000011101011010000010
1000001011101000010000001
1000000100101000100000001
1000000011000111000000001
1000110000010000001100001
1001000000101100000010001
1001010001000010001001001
1000001001000100010000001
0100001100111000110000010
0100000110000001100000010
0010000101111110100000100
0010000010000001000000100
0001000001011010000001000
0000100000111100000010000
0000011000000000001100000
0000000110000000110000000
0000000001111111000000000
输出文件名: xl.out
1