光芒万丈的数学之光
数学是伟大的科学金字塔的基础。伟大的智慧和光明之神为了能够展示数学的光辉,共同制造了数学神殿,数学神殿会向外发出闪耀的光辉。照耀到数学光辉的山,一定能够更快的发展。
但终究光是无法穿越大山的,根据光是直线传播的原理,一座被照到的山后面将无法再被数学之光找到(所谓后面的定义自然符合光传播原理)。而在题目中,所有的山都被抽象成一个点。
请你替伟大的智慧和光明之神,数一下,到底有多少个有数学信徒的山可以接受到数学之光的照耀?
输入第一行包括两个正整数m和n(m * n < 1000000),分别表示这个“世界”的长和宽。而下面的m行,每行都有n 个符号表示这个世界在这个位置的地理状态。
分别用三种符号表示状态。
符号点“.”:表示没有人烟的沙漠。
符号M"M":表示有信徒的山脉。
符号S"S":表示数学神殿。
输出能够照到的文明山数量。
输入样例1:
4 6
S.MM.
....M
.....
.....
输入样例2:
4 6
.S.MM.
...MM.
.....M
......
输出样例1:
2
输出样例2:
3
【样例说明】
样例1说明:第一行第4个位置上的山被挡住了!所以没有找到数学之光。
样例2说明:第一行第4个位置上的山被挡住了!第三行的山被第二行第4个位置上的山挡住了。