02386: Lake Counting

Due to recent rains, water has pooled in various places in Farmer John's field, which is represented by a rectangle of N x M (1 <= N <= 100; 1 <= M <= 100) squares. Each square contains either water ('W') or dry land ('.'). Farmer John would like to figure out how many ponds have formed in his field. A pond is a connected set of squares with water in them, where a square is considered adjacent to all eight of its neighbors.

Given a diagram of Farmer John's field, determine how many ponds he has.

输入

* Line 1: Two space-separated integers: N and M

* Lines 2..N+1: M characters per line representing one row of Farmer John's field. Each character is either 'W' or '.'. The characters do not have spaces between them.

输出

* Line 1: The number of ponds in Farmer John's field.

样例输入

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

样例输出

提示

OUTPUT DETAILS:

There are three ponds: one in the upper left, one in the lower left,and one along the right side.

来源: USACO 2004 November

python

#1.dfs
import sys

# input = sys.stdin.read
sys.setrecursionlimit(20000)


def dfs(x, y):
    # 标记当前位置为已访问
    field[x][y] = '.'
    # 遍历8个方向
    for dx, dy in directions:
        nx, ny = x + dx, y + dy
        # 检查新位置是否在地图范围内且未被访问
        if 0 <= nx < n and 0 <= ny < m and field[nx][ny] == 'W':
            dfs(nx, ny)


# 一次性读取所有输入
# data = input().split()
# n, m = map(int, data[:2])
# field = [list(row) for row in data[2:2+n]]
n, m = map(int, input().split())
field = [list(input()) for _ in range(n)]
# 初始化8个方向
directions = [(-1, -1), (-1, 0), (-1, 1), (0, -1), (0, 1), (1, -1), (1, 0), (1, 1)]
# 计数器
cnt = 0

# 遍历地图
for i in range(n):
    for j in range(m):
        if field[i][j] == 'W':
            dfs(i, j)
            cnt += 1

print(cnt)

通过使用栈来模拟递归，可以避免因递归过深导致的栈溢出问题。

python

def dfs(x, y):
    stack = [(x, y)]
    while stack:
        x, y = stack.pop()
        if field[x][y] != 'W':
            continue
        field[x][y] = '.'  # 标记当前位置为已访问
        for dx, dy in directions:
            nx, ny = x + dx, y + dy
            if 0 <= nx < n and 0 <= ny < m and field[nx][ny] == 'W':
                stack.append((nx, ny))

# 读取输入
n, m = map(int, input().split())
field = [list(input()) for _ in range(n)]

# 初始化8个方向
directions = [(-1, -1), (-1, 0), (-1, 1), (0, -1), (0, 1), (1, -1), (1, 0), (1, 1)]

# 计数器
cnt = 0

# 遍历地图
for i in range(n):
    for j in range(m):
        if field[i][j] == 'W':
            dfs(i, j)
            cnt += 1

print(cnt)

python

#2.bfs
from collections import deque
def bfs(x,y):
    queue=deque([(x,y)])
    while queue:
    	#把各个方向走一步试万再走下一步
        x,y=queue.popleft()
        field[x][y] = '.'
        for k in range(8):
            nx, ny = x + dx[k], y + dy[k]
            if 0 <= nx < n and 0 <= ny < m \
                    and field[nx][ny] == 'W':
                #添加进队列并标记
                queue.append((nx,ny))
                field[nx][ny] = '.'
n,m=map(int,input().split())
field=[list(input()) for _ in range(n)]
cnt=0
dx=[-1,-1,-1,0,0,1,1,1]
dy=[-1,0,1,-1,1,-1,0,1]
for i in range(n):
    for j in range(m):
        if field[i][j]=='W':
            bfs(i,j)
            cnt+=1
print(cnt)

02386: Lake Counting ​

02386: Lake Counting