代码随想录算法训练营DAY58｜101.孤岛的总面积、102.沉没孤岛、103. 水流问题、104.建造最大岛屿

忙。。。写了好久。。。。慢慢补吧。

101.孤岛的总面积

• 先把周边的岛屿变成水
• dfs

def dfs(x, y, graph, s):
    if x<0 or x>=len(graph) or y<0 or y>=len(graph[0]) or graph[x][y]==0:
        return s
    graph[x][y]=0
    s+=1
    s = dfs(x+1, y, graph, s)
    s = dfs(x-1, y, graph, s)
    s = dfs(x, y+1, graph, s)
    s = dfs(x, y-1, graph, s)
    return s


if __name__=='__main__':
    n,m = map(int,input().split())
    graph=[]
    for i in range(n):
        row = list(map(int, input().split()))
        graph.append(row)
        
    for i in range(n):
        if graph[i][0]==1:
            dfs(i,0,graph,0)
        if graph[i][m-1]==1:
            dfs(i,m-1,graph,0)
    for j in range(m):
        if graph[0][j]==1:
            dfs(0,j,graph,0)
        if graph[n-1][j]==1:
            dfs(n-1,j,graph,0)
            
    s_t = 0
    for x in range(n):
        for y in range(m):
            if graph[x][y]==1:
                s=dfs(x,y,graph,0)
                s_t+=s
    
    print(s_t)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

102.沉没孤岛

from collections import deque

def bfs(x, y, graph):
    graph[x][y]=2
    que = deque([[x,y]])
    while que:
        x, y = que.popleft()
        directions = [[0,1],[0,-1],[1,0],[-1,0]]
        for k in range(4):
            x0, y0 = directions[k]
            new_x = x+x0
            new_y = y+y0
            if new_x>=0 and new_x<len(graph) and new_y>=0 and new_y<len(graph[0]) and graph[new_x][new_y]==1:
                que.append([new_x, new_y])
                graph[new_x][new_y]=2
    return     



if __name__=='__main__':
    n,m = map(int,input().split())
    
    graph=[]
    for _ in range(n):
        row = list(map(int, input().split()))
        graph.append(row)    
  
    for i in range(n):
        if graph[i][0]==1:
            bfs(i,0,graph)
        if graph[i][m-1]==1:
            bfs(i,m-1,graph)
    
    for j in range(m):
        if graph[0][j]==1:
            bfs(0,j,graph)
        if graph[n-1][j]==1:
            bfs(n-1,j,graph)
 
    for x in range(n):
        for y in range(m):
            if graph[x][y]==2:
                graph[x][y]=1
            elif graph[x][y]==1:
                graph[x][y]=0
    
    for a in range(n):
        for b in range(m):
            print(str(graph[a][b])+' ',end = '')
        print()
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50

103. 水流问题

• 注意是从边界逆流而上，判断条件应该是graph[x][y]<=graph[new_x][new_y]:

def dfs(x,y,graph,bordermatrix):
    if bordermatrix[x][y]:
        return
    bordermatrix[x][y]=1
    directions=[[0,1],[0,-1],[1,0],[-1,0]]
    for i in range(4):
        x0,y0=directions[i]
        new_x = x+x0
        new_y = y+y0
        if new_x<0 or new_x>=len(graph) or new_y<0 or new_y>=len(graph[0]):
            continue
        if graph[x][y]<=graph[new_x][new_y]:
            dfs(new_x,new_y,graph,bordermatrix)
    return 
    


if __name__=='__main__':
    n,m=map(int, input().split())
    
    graph=[]
    for _ in range(n):
        row = list(map(int, input().split()))
        graph.append(row)
        
    firstborder=[[0]*m for i in range(n)]
    secondborder=[[0]*m for i in range(n)]
    
    for i in range(n):
        dfs(i,0,graph,firstborder)
        dfs(i,m-1,graph,secondborder)
    
    for j in range(m):
        dfs(0,j,graph,firstborder)
        dfs(n-1,j,graph,secondborder)
    
    for k in range(n):
        for l in range(m):
            if firstborder[k][l] and secondborder[k][l]:
                print('{} {}'.format(str(k),str(l)))
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

104.建造最大岛屿

def dfs(x,y,graph,visited,mark,s):
    directions=[[0,1],[0,-1],[1,0],[-1,0]]
    if visited[x][y] or not graph[x][y]:
        return  s
    visited[x][y]=True
    graph[x][y]=mark
    s+=1
    for i in range(4):
        x0,y0=directions[i]
        new_x = x+x0
        new_y = y+y0
        if new_x<0 or new_x>=len(graph) or new_y<0 or new_y>=len(graph[0]):
            continue
        s = dfs(new_x,new_y,graph,visited,mark,s)
    return s
    
if __name__=='__main__':
    n,m = map(int, input().split())
    
    graph = []
    for i in range(n):
        row = list(map(int, input().split()))
        graph.append(row)
    
    isallgrid=True
    visited=[[False]*m for i in range(n)]
    islands={}
    islands[0]=0
    idx=1
    for j in range(n):
        for k in range(m):
            if graph[j][k]==1:
                s = dfs(j,k,graph,visited,idx,0)
                islands[idx]=s
                idx+=1
            else:
                isallgrid=False
                
    if isallgrid:
        print(m*n)
    else:
        result = 0
        for j in range(n):
            for k in range(m):
                count = 1
                visitedgraph=[]
                if graph[j][k]==0:
                    directions=[[0,1],[0,-1],[1,0],[-1,0]]
                    for l in range(4):
                        j0,k0 = directions[l]
                        new_j = j+j0
                        new_k = k+k0
                        if new_j<0 or new_j>=len(graph) or new_k<0 or new_k>=len(graph[0]):
                            continue
                        if graph[new_j][new_k] in visitedgraph: continue
                        count+=islands[graph[new_j][new_k]]
                        visitedgraph.append(graph[new_j][new_k])
                result = max(result, count)
                
        print(result)

                
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62