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)

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 完成