网站页面
当前课程
成员
General
主题 1
主题 2
主题 4
主题 5
主题 6
主题 7
主题 8
主题 9
主题 10
主题 11
主题 12
主题 13
主题 14
主题 15
主题 16
主题 17
主题 18
主题 19
主题 20
[IPSC2001]笑脸
成绩 | 0 | 开启时间 | 2013年02月21日 星期四 23:02 |
折扣 | 0.8 | 折扣时间 | 2013年02月28日 星期四 23:02 |
允许迟交 | 是 | 关闭时间 | 2013年02月28日 星期四 23: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
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