题解 | 剪纸游戏

from re import M
import sys
from collections import deque
dirs = [(1,0), (-1,0), (0,1), (0,-1)]
# 判断这个区间内是不是都是矩形
def judge(ma,mi):
    for i in range(mi[0],ma[0]+1):
        for j in range(mi[1],ma[1]+1):
            if grid2[i][j] == '*':
                return 0
    return 1

def DFS(x,y,ma,mi):
    grid[x][y] = '*'
    ma[0] = max(x, ma[0])
    ma[1] = max(y, ma[1])
    mi[0] = min(x, mi[0])
    mi[1] = min(y, mi[1])
    for dx,dy in dirs:
        nx,ny = x+dx,y+dy
        if 0<=nx<r and 0<=ny<c and grid[nx][ny] == '.':
            DFS(nx,ny,ma,mi)



r , c = map(int,input().split())
grid = []
for _ in range(r):
    grid.append(list(input()))
grid2 = [st.copy() for st in grid]

res = []
# ===================== 核心：无函数 BFS =====================
for i in range(r):
    for j in range(c):
        if grid[i][j] == '.':
            # BFS 初始化
            q = deque()
            q.append((i, j))
            grid[i][j] = '*'
            
            # 当前连通块的最大/最小坐标
            ma = [i, j]
            mi = [i, j]
            
            # BFS 循环
            while q:
                x, y = q.popleft()
                
                # 更新最大最小
                if x > ma[0]: ma[0] = x
                if y > ma[1]: ma[1] = y
                if x < mi[0]: mi[0] = x
                if y < mi[1]: mi[1] = y
                
                # 四个方向
                for dx, dy in dirs:
                    nx = x + dx
                    ny = y + dy
                    if 0 <= nx < r and 0 <= ny < c and grid[nx][ny] == '.':
                        grid[nx][ny] = '*'
                        q.append((nx, ny))
            
            res.append([ma, mi])
cnt = 0
for ma,mi in res:
    if judge(ma,mi):
        cnt+=1
print(cnt)