题解 | 剪纸游戏

DFS会爆栈

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 = []
for i in range(r):
    for j in range(c):
        if grid[i][j] == '.':
            ma = [i,j]
            mi = [i,j]
            DFS(i,j,ma,mi)
            res.append([ma,mi])
cnt = 0
for ma,mi in res:
    if judge(ma,mi):
        cnt+=1
print(cnt)