问题1543--别踩黑块!

1543: 别踩黑块!

时间限制: 1Sec 内存限制:128 MB
提交:19 解决:4
[ 状态] [ 讨论版] [ 提交] [命题人: ]
题目描述
最近,chenyao迷上了一款叫做“别踩白块”的游戏,但是手残的他每次都撑不过10s,这使他非常自卑,于是决定出一道题来报复所有游戏玩得比他好的人,题目如下:
  在“别踩白块”游戏中,黑白块交替出现,每一个单位只能是黑块或者白块,chenyao把整张游戏图上黑白块顺序打乱,并重新生成在一张n行,m列的图。规定在区域(a, b) ~ (c, d)(c>=a & d>=b)内所有的颜色一样的方块组成一个矩形(一个大矩形可能包含多个小矩形),为了避免点击这些矩形,你需要在规定时间内将所有矩形统计出来(包括相互包含的矩形)
输入
每组数据包含多组测试。
每组测试第一行两个整数,为n,m( 1 <= m , n <= 1000)
接下来n行,每行m个字符,包含且仅限于'B'与'W',分别表示黑块与白块
输出
一行一个整数为所有的黑色矩形个数
样例输入 Copy
2 2 WB BW 3 4 WBBW WBWB WBBW
样例输出 Copy
2 11
提示
对于第一组测试,仅有(1,2)~(1,2) 与(2,1)~(2,1)两个矩形
对于第二组测试,
第一行有3个矩形,第二行有2个矩形,第三行有3个矩形
第二列有6个矩形,第三列有2个矩形,第四列有1个矩形
根据容斥原理,共有11个矩形
来源/分类