Counting Rooms

這種題目不是一般常見的樹狀圖或其他有節點的圖，而是自訂的迷宮圖，這種題目常見的解法就是用bfs,dfs去跑，另開一個visited來記錄走過的。

詳細：https://hackmd.io/@HyC-1029/rkwgn3OWeg

Flood Fill 演算法

從目前的點向四周擴散，像洪水一樣因而得名。

遍歷整張地圖，每當你發現一個還沒走過的 '.'，就：

1. 當作一個新房間
2. 用 DFS 或 BFS 從這格往四周延伸，全部標記成 visited
3. 把房間數量加一

n, m = map(int, input().split())
gr = [list(input()) for _ in range(n)]
visited = [[False]*m for _ in range(n)]

# 上下左右
dirs = [(-1, 0), (1, 0), (0, -1), (0, 1)]

def dfs(x, y):
    visited[x][y] = True
    for dx, dy in dirs:
        nx, ny = x + dx, y + dy
        if 0 <= nx < n and 0 <= ny < m: # 確保在邊界內
            if gr[nx][ny] == '.' and not visited[nx][ny]:
                dfs(nx, ny) # 遞迴標記

room = 0
for i in range(n):
    for j in range(m):
        if gr[i][j] == '.' and not visited[i][j]:
            dfs(i, j)
            room += 1

print(room)

結果當m,n 都是1000時就會超時了，因為這遠遠超出了python遞迴的極限。

待