枚举每个二维点

# [USACO19JAN] Icy Perimeter S

冰淇淋的面积用dfs很好求

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

难点在于求联通快的周长

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

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

Part 1 求出最大连通块面积

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

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

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

9
q = deque()
10
# 枚举每个二维点
11
for i in range(1, n + 1):
12
    for j in range(1, n + 1):
13
        if not vis[i][j]:
14
            # [todo] 还需要求出最大联通块的面积
15
            area = 0
9 collapsed lines
16
            q.append((i, j))
17
            while len(q):
18
                u = q.popleft() # 例如 u = (5, 7)
19
                area += 1
20
                for d in dir:
21
                    # 怎么拿出 d 里面的第一个元素和第二个元素？
22
                    v = (u[0] + d[0], u[1] + d[1])
23
                    if 1 <= v[0] <= n and 1 <= v[1] <= n and a[v[0]][v[1]] == '#' and not vis[v[0]][v[1]]:
24
                        q.append(v)

1
n = 读入整数
2
a = []
3
for _ in range(n):
4
    a.append(input())
5

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

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

10
def dfs(x, y):
11
    global area
12
    area += 1
13
    vis[x][y] = True # 走过了
14
    for dx, dy in dir:
15
        tx, ty = x + dx, y + dy  # 要到达的点
11 collapsed lines
16
        # tx, ty 必须没走过
17
        if 0 <= tx <= n - 1 and 0 <= ty <= n - 1 and a[tx][ty] == '#' and not vis[tx][ty]: # 合法
18
            dfs(tx, ty)
19

20
max_area = 0
21
for i in range(n):
22
    for j in range(n):
23
        if not vis[i][j]:
24
            area = 0
25
            dfs(i, j)
26
            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 完成