＜代码随想录＞ 算法训练营-2025.01.03

思路：当判断当前岛屿已经触及边缘时，仍然遍历标记，但最后返回面积时返回0，使用flag标识有没有触及边缘

#所有单元格都不接触边缘 如果触及边缘时使面积返回0
from collections import deque
def countArea(i,j,graph,n,m):
    flag=1 
    dq=deque()
    dq.append([i,j])
    graph[i][j]=-1
    tempRes=1
    while len(dq)>0:
        temp=dq.popleft()
        if temp[0]==0 or temp[0]==n-1 or temp[1]==0 or temp[1]==m-1:
            flag=0
        if temp[0]>0 and graph[temp[0]-1][temp[1]]==1:
            graph[temp[0]-1][temp[1]]=-1
            dq.append([temp[0]-1,temp[1]])
            tempRes+=1
        if temp[0]<n-1 and graph[temp[0]+1][temp[1]]==1:
            graph[temp[0]+1][temp[1]]=-1
            dq.append([temp[0]+1,temp[1]])
            tempRes+=1
        
        if temp[1]>0 and graph[temp[0]][temp[1]-1]==1:
            graph[temp[0]][temp[1]-1]=-1
            dq.append([temp[0],temp[1]-1])
            tempRes+=1
        if temp[1]<m-1 and graph[temp[0]][temp[1]+1]==1:
            graph[temp[0]][temp[1]+1]=-1
            dq.append([temp[0],temp[1]+1])
            tempRes+=1
    if flag==0:
        return flag
    else:
        return tempRes
            

def main():
    n,m=map(int,input().split())
    graph=[[0]*m for _ in range(n)]
    for i in range(n):
        graph[i]=list(map(int,input().split()))
    res=0    
    for i in range(n):
        for j in range(m):
            if graph[i][j]==1:
                res+= countArea(i,j,graph,n,m)
                
    print(res)
    

if __name__=="__main__":
    main()

# 先判断是不是孤岛 如果是孤岛才标记（先记录一下）
#实际做法是 先标记（避免死循环）且记录，如果不是孤岛就再变回1
from collections import deque
def countArea(i,j,graph,n,m):
    flag=1 
    dq=deque()
    
    dq.append([i,j])
    graph[i][j]=0
    tempRes=[[i,j]]
    while len(dq)>0:
        temp=dq.popleft()
        if temp[0]==0 or temp[0]==n-1 or temp[1]==0 or temp[1]==m-1:
            flag=0
        if temp[0]>0 and graph[temp[0]-1][temp[1]]==1:
            graph[temp[0]-1][temp[1]]=0
            dq.append([temp[0]-1,temp[1]])
            tempRes.append([temp[0]-1,temp[1]])
        if temp[0]<n-1 and graph[temp[0]+1][temp[1]]==1:
            graph[temp[0]+1][temp[1]]=0
            dq.append([temp[0]+1,temp[1]])
            tempRes.append([temp[0]+1,temp[1]])
        
        if temp[1]>0 and graph[temp[0]][temp[1]-1]==1:
            graph[temp[0]][temp[1]-1]=0
            dq.append([temp[0],temp[1]-1])
            tempRes.append([temp[0],temp[1]-1])
        if temp[1]<m-1 and graph[temp[0]][temp[1]+1]==1:
            graph[temp[0]][temp[1]+1]=0
            dq.append([temp[0],temp[1]+1])
            tempRes.append([temp[0],temp[1]+1])
    if flag==0:
        for a,b in tempRes:
            graph[a][b]=1
    return
            

def main():
    n,m=map(int,input().split())
    graph=[[0]*m for _ in range(n)]
    for i in range(n):
        graph[i]=list(map(int,input().split()))
      
    for i in range(n):
        for j in range(m):
            if graph[i][j]==1:
                countArea(i,j,graph,n,m)
    for i in range(n):
        print(' '.join(str(item) for item in graph[i]))
    
    

if __name__=="__main__":
    main()

正确题解：

first = set()
second = set()
directions = [[-1, 0], [0, 1], [1, 0], [0, -1]]

def dfs(i, j, graph, visited, side):
    if visited[i][j]:
        return
    
    visited[i][j] = True
    side.add((i, j))
    
    for x, y in directions:
        new_x = i + x
        new_y = j + y
        if (
            0 <= new_x < len(graph)
            and 0 <= new_y < len(graph[0])
            and int(graph[new_x][new_y]) >= int(graph[i][j])
        ):
            dfs(new_x, new_y, graph, visited, side)

def main():
    global first
    global second
    
    N, M = map(int, input().strip().split())
    graph = []
    for _ in range(N):
        row = input().strip().split()
        graph.append(row)
    
    # 是否可到达第一边界
    visited = [[False] * M for _ in range(N)]
    for i in range(M):
        dfs(0, i, graph, visited, first)
    for i in range(N):
        dfs(i, 0, graph, visited, first)
    
    # 是否可到达第二边界
    visited = [[False] * M for _ in range(N)]
    for i in range(M):
        dfs(N - 1, i, graph, visited, second)
    for i in range(N):
        dfs(i, M - 1, graph, visited, second)

    # 可到达第一边界和第二边界
    res = first & second
    
    for x, y in res:
        print(f"{x} {y}")
    
    
if __name__ == "__main__":
    main()

自己的错误题解：

#从每个点深搜，能同时到达上左和下右

#可以不可以倒着来第一边界能到的点拉出来 第二边界能找的点也拉出来
# 第一边界 [0][j]    [i][0] 
# 第二边界 [n-1][j]  [i][m-1]

from collections import deque
def mark(i,j,graph,n,m,flag):
    dq=deque()
    dq.append([i,j])
    tempRes=[[i,j]]
    while len(dq)>0:
        a,b=dq.popleft()
        if flag==1:
            if a<n-1 and graph[a+1][b]>=graph[a][b]:
                dq.append([a+1,b])
                tempRes.append([a+1,b])
            if b<m-1 and graph[a][b+1]>=graph[a][b]:
                dq.append([a,b+1])
                tempRes.append([a,b+1])
        else:
            if a>0 and graph[a-1][b]>=graph[a][b]:
                dq.append([a-1,b])
                tempRes.append([a-1,b])
            if b>0 and graph[a][b-1]>=graph[a][b]:
                dq.append([a,b-1])
                tempRes.append([a,b-1]) 
    
    return tempRes
        
            

def main():
    n,m=map(int,input().split())
    graph=[[0]*m for _ in range(n)]
    for i in range(n):
        graph[i]=list(map(int,input().split()))
    res=[]
    first=[]
    second=[]
    for i in range(n):
        first+=mark(i,0,graph,n,m,1)
        second+=mark(i,m-1,graph,n,m,2)
    for j in range(m):
        first+=(mark(0,j,graph,n,m,1))
        second+=(mark(n-1,j,graph,n,m,2))
    res=list(filter(lambda x: x in first, second))
    res=[list(item) for item in set(tuple(r) for r  in res)]
        
    
    for r in res:
        print(' '.join(str(item) for item in r))

if __name__=="__main__":
    main()

#暴力解：遍历每个非1点，将其变为1后，求一次从该点出发的最大岛屿
#优化思路：
#1.给岛屿打标，记录不同标记的岛屿的面积
#2.将一个0点变成1，合并相邻点岛屿的面积
direction=[[-1,0],[1,0],[0,-1],[0,1]]

def countArea(i,j,graph,n,m,mark):
    area=0
    if graph[i][j]==1:
        area+=1
        graph[i][j]=mark
        for d in direction:
            x=i+d[0]
            y=j+d[1]
            if 0<=x<=n-1 and 0<=y<=m-1:
                area+=countArea(x,y,graph,n,m,mark)
    
    return area
    
def main():
    n,m=map(int,input().split())
    graph=[[0]*m for _ in range(n)]
    for i in range(n):
        graph[i]=list(map(int,input().split()))
    mark=2
    dict={}
    for i in range(n):
        for j in range(m):
            if graph[i][j]==1:
                area=countArea(i,j,graph,n,m,mark)
                dict[mark]=area
                mark+=1
    res=0
    if len(dict)>0:
        res=max(dict.values())
    for i in range(n):
        for j in range(m):
            if graph[i][j]==0:
                tempRes=1
                visited=set()
                for d in direction:
                    x=i+d[0]
                    y=j+d[1]
                    if 0<=x<=n-1 and 0<=y<=m-1 and graph[x][y]!=0 and graph[x][y] not in visited :
                        visited.add(graph[x][y])
                        tempRes+=dict[graph[x][y]]
                res=max(res,tempRes)
    print(res)
    
if __name__=="__main__":
    main()