问题1543--别踩黑块!

1543: 别踩黑块!

时间限制: 1 Sec  内存限制: 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个矩形
来源/分类