250104

# [USACO19JAN] Icy Perimeter S

冰淇淋的面积用dfs很好求

只要算出每个联通块中'#'的个数即可

难点在于求联通快的周长

观察一下样例 发现周长就是每个'#'周围'.'或超过边界的方块个数

解决这一问题后这道题几乎就是一道dfs裸题了

• Part 1 求出最大连通块面积

读入 n
dir = [(0, 1), (0, -1), (1, 0), (-1, 0)]
a 数组从 1, 1 开始，存储 (i, j) 是 '#' 还是 '.'
二维数组 vis = (n + 10) * (n + 10) 的数组表示 i, j 是否访问过

q = deque()
# 枚举每个二维点
for i in range(1, n + 1):
    for j in range(1, n + 1):
        if i, j 没有访问过，
            # [todo] 还需要求出最大联通块的面积
            area = 0
            q.append((i, j))
            while len(q):
                u = q.popleft() # 例如 u = (5, 7)
                area += 1
                for d in dir:
                    # 怎么拿出 d 里面的第一个元素和第二个元素？
                    v = (u[0] + d[0], u[1] + d[1])
                    if 1 <= v[0] <= n and 1 <= v[1] <= n and a[v[0]][v[1]] == '#' and not vis[v[0]][v[1]]:
                        q.append(v)

读入 n
dir = [(0, 1), (0, -1), (1, 0), (-1, 0)]
a 数组从 1, 1 开始，存储 (i, j) 是 '#' 还是 '.'
a = []
for i in range(n):
    a.append(' ' + input())
vis = [[0] * (n + 1) for _ in range(n + 1)]

q = deque()
# 枚举每个二维点
for i in range(1, n + 1):
    for j in range(1, n + 1):
        if not vis[i][j]:
            # [todo] 还需要求出最大联通块的面积
            area = 0
            q.append((i, j))
            while len(q):
                u = q.popleft() # 例如 u = (5, 7)
                area += 1
                for d in dir:
                    # 怎么拿出 d 里面的第一个元素和第二个元素？
                    v = (u[0] + d[0], u[1] + d[1])
                    if 1 <= v[0] <= n and 1 <= v[1] <= n and a[v[0]][v[1]] == '#' and not vis[v[0]][v[1]]:
                        q.append(v)

n = 读入整数
a = []
for _ in range(n):
    a.append(input())

vis = 全是 False 的 n * n 的二维数组

dir = [(0, 1), (1, 0), (-1, 0), (0, -1)]

def dfs(x, y):
    global area
    area += 1
    vis[x][y] = True # 走过了
    for dx, dy in dir:
        tx, ty = x + dx, y + dy  # 要到达的点
        # tx, ty 必须没走过
        if 0 <= tx <= n - 1 and 0 <= ty <= n - 1 and a[tx][ty] == '#' and not vis[tx][ty]: # 合法
            dfs(tx, ty)

max_area = 0
for i in range(n):
    for j in range(n):
        if not vis[i][j]:
            area = 0
            dfs(i, j)
            print(area)

Problem 3. Problem 1. Marathon

这道题目是一道动规的题目。

令f[i][j]代表到了第i个检查点，跳过了j个的最短距离。

f[i][j]=min(f[i-l-1][j-l]+dis(i,i-l-1))

复杂度为 O(n^3)

课堂总结

dfs 完成