18108: 池塘数目

matrices/dfs similar, http://cs101.openjudge.cn/practice/1980

一场暴雨之后，农田里形成了大大小小的池塘。农田用N×M个格子表示，格子有两种状态，有水('W')和无水('.')。相邻两个有水的格子属于一个池塘，一个格子被视作和它周围八个格子都相邻。

现在需要数出在农田里有多少个池塘。

输入

第一行是一个整数，表示一共有 T 组数据。每组第一行包含两个整数N和M。接下来的N行，每行有M个字符('W'或者'.')，表示格子的当前状态。字符之间没有空格。

输出

每组数据对应一行，输出农田里的池塘数目。

样例输入

2
2 2
W.
.W
10 12
W........WW.
.WWW.....WWW
....WW...WW.
.........WW.
.........W..
..W......W..
.W.W.....WW.
W.W.W.....W.
.W.W......W.
..W.......W.

样例输出

1
3

提示

说明：如果只有一个W，也是一个池塘。

来源：cs101-2016 期末机考备选

思路：设一个函数，将到访过的W标记，然后如果周围没有被标记的W就是新的池塘。用for loop每个地方过一遍就懂有几个池塘了。

2020fall-cs101，汪元正。解题思路：此题便是要算图中连通分支个数。

python

dir = [[-1, 0], [1, 0], [0, -1], [0, 1], [-1, -1], [-1, 1], [1, -1], [1, 1]]
def dfs(x, y):
	if x < 0 or x >= N or y < 0 or y >= M or board[x][y] != 'W':
		return
	board[x][y] = '.'
	for i in range(len(dir)):
		dfs(x + dir[i][0], y + dir[i][1])
	
T = int(input())
while T!=0:
	T -= 1	
	N, M = map(int, input().split())
	board = []
	ans = 0
	for i in range(N):
		board.append(list(input()))
	for i in range(N):
		for j in range(M):
			if board[i][j] == 'W':
				ans += 1
				dfs(i, j)
	print(ans)

18108: 池塘数目 ​

18108: 池塘数目