1
import sys
2
sys.setrecursionlimit(10**7)
3
input = sys.stdin.read
4

5
def main():
6
    data = input().split()
7
    n, m = int(data[0]), int(data[1])
8
    index = 2
9
    graph = [[0] * m for _ in range(n)]
10
    for i in range(n):
11
        for j in range(m):
12
            graph[i][j] = int(data[index])
13
            index += 1
14
    visited = [[False] * m for _ in range(n)]
15

16
    def dfs(x, y):
17
        if x < 0 or x >= n or y < 0 or y >= m:
18
            return 0, True
19
        if graph[x][y] == 0 or visited[x][y]:
20
            return 0, False
21
        visited[x][y] = True
22
        area = 1
23
        touches_edge = False
24

25
        for nx, ny in [(x-1,y), (x+1,y), (x,y-1), (x,y+1)]:
26
            sub_area, sub_touch = dfs(nx, ny)
27
            area += sub_area
28
            if sub_touch:
29
                touches_edge = True
30

31
        if x == 0 or x == n-1 or y == 0 or y == m-1:
32
            touches_edge = True
33

34
        return area, touches_edge
35

36
    total_area = 0
37
    for i in range(n):
38
        for j in range(m):
39
            if graph[i][j] == 1 and not visited[i][j]:
40
                area, touches_edge = dfs(i, j)
41
                if not touches_edge:
42
                    total_area += area
43

44
    print(total_area)
45

46
main()

1
import sys
2
input = sys.stdin.read
3
sys.setrecursionlimit(10**7)
4

5
def main():
6
    data = input().split()
7
    n, m = int(data[0]), int(data[1])
8
    index = 2
9
    graph = [[0] * m for _ in range(n)]
10
    for i in range(n):
11
        for j in range(m):
12
            graph[i][j] = int(data[index])
13
            index += 1
14

15
    visited = [[False] * m for _ in range(n)]
16

17
    def dfs(x, y):
18
        if x < 0 or x >= n or y < 0 or y >= m:
19
            return
20
        if graph[x][y] == 0 or visited[x][y]:
21
            return
22
        visited[x][y] = True
23
        dfs(x - 1, y)
24
        dfs(x + 1, y)
25
        dfs(x, y - 1)
26
        dfs(x, y + 1)
27

28
    # 从边缘陆地开始，标记所有连通陆地为非孤岛
29
    for i in range(n):
30
        for j in range(m):
31
            if (i == 0 or j == 0 or i == n - 1 or j == m - 1) and graph[i][j] == 1 and not visited[i][j]:
32
                dfs(i, j)
33

34
    # 沉没孤岛（未访问的陆地变为水）
35
    for i in range(n):
36
        for j in range(m):
37
            if graph[i][j] == 1 and not visited[i][j]:
38
                graph[i][j] = 0
39

40
    # 输出矩阵，注意每个元素后面有空格
41
    for i in range(n):
42
        print(' '.join(str(cell) for cell in graph[i]) + ' ')
43

44
main()

1
import sys
2
from collections import deque
3
input = sys.stdin.read
4

5
def main():
6
    data = input().split()
7
    n, m = int(data[0]), int(data[1])
8
    matrix = []
9
    index = 2
10
    for _ in range(n):
11
        row = list(map(int, data[index:index+m]))
12
        index += m
13
        matrix.append(row)
14

15
    def bfs(starts):
16
        visited = [[False]*m for _ in range(n)]
17
        queue = deque(starts)
18
        for x, y in starts:
19
            visited[x][y] = True
20
        directions = [(1,0), (-1,0), (0,1), (0,-1)]
21
        while queue:
22
            x, y = queue.popleft()
23
            for dx, dy in directions:
24
                nx, ny = x + dx, y + dy
25
                if 0 <= nx < n and 0 <= ny < m:
26
                    if not visited[nx][ny] and matrix[nx][ny] >= matrix[x][y]:
27
                        visited[nx][ny] = True
28
                        queue.append((nx, ny))
29
        return visited
30

31
    first_border = [(i, 0) for i in range(n)] + [(0, j) for j in range(m)]
32
    second_border = [(i, m-1) for i in range(n)] + [(n-1, j) for j in range(m)]
33

34
    reachable_first = bfs(first_border)
35
    reachable_second = bfs(second_border)
36

37
    result = []
38
    for i in range(n):
39
        for j in range(m):
40
            if reachable_first[i][j] and reachable_second[i][j]:
41
                result.append((i, j))
42

43
    for x, y in result:
44
        print(x, y)
45

46
main()

1
import sys
2
sys.setrecursionlimit(10**7)
3
input = sys.stdin.read
4

5
def main():
6
    data = input().split()
7
    n, m = int(data[0]), int(data[1])
8
    index = 2
9
    grid = []
10
    for _ in range(n):
11
        row = list(map(int, data[index:index+m]))
12
        index += m
13
        grid.append(row)
14

15
    # 岛屿id起始为2（因为0、1已用）
16
    island_id = 2
17
    area_map = {}  # id -> 面积
18

19
    def dfs(x, y, id):
20
        stack = [(x, y)]
21
        grid[x][y] = id
22
        area = 0
23
        while stack:
24
            cx, cy = stack.pop()
25
            area += 1
26
            for nx, ny in [(cx-1,cy),(cx+1,cy),(cx,cy-1),(cx,cy+1)]:
27
                if 0 <= nx < n and 0 <= ny < m and grid[nx][ny] == 1:
28
                    grid[nx][ny] = id
29
                    stack.append((nx, ny))
30
        return area
31

32
    # 标记岛屿并计算面积
33
    for i in range(n):
34
        for j in range(m):
35
            if grid[i][j] == 1:
36
                area = dfs(i, j, island_id)
37
                area_map[island_id] = area
38
                island_id += 1
39

40
    # 如果没有0，说明整张图都是陆地，直接输出面积即可
41
    max_area = max(area_map.values()) if area_map else 0
42

43
    # 遍历0，计算变成1后可能最大面积
44
    for i in range(n):
45
        for j in range(m):
46
            if grid[i][j] == 0:
47
                neighbor_ids = set()
48
                for nx, ny in [(i-1,j),(i+1,j),(i,j-1),(i,j+1)]:
49
                    if 0 <= nx < n and 0 <= ny < m and grid[nx][ny] > 1:
50
                        neighbor_ids.add(grid[nx][ny])
51
                area_sum = 1  # 把当前0变1
52
                for id in neighbor_ids:
53
                    area_sum += area_map[id]
54
                max_area = max(max_area, area_sum)
55

56
    print(max_area)
57

58
main()