代码随想录算法训练营day52 day53| 卡码网101.孤岛的总面积 102.沉没孤岛 103.水流问题 104.建造最大岛屿 110.字符串接龙 105.有向图的完全可达性

# 用深搜，遍历邻接矩阵的四个边，先遍历所有可遍历的岛屿，把这些遍历到的陆地变成海洋
# 那么后续如果还有未遍历的岛就肯定是孤岛
directions = [[1,0],[-1,0],[0,1],[0,-1]]
result = 0

def dfs(grids, x, y):
    grids[x][y] = 0 # 本题将边界处岛屿都变成海洋
    global result
    result += 1
    
    for i,j in directions:
        cur_x = x+i
        cur_y = y+j
        # 若索引超出边界就终止
        if cur_x<0 or cur_x>=len(grids) or cur_y<0 or cur_y>=len(grids[0]):
            continue
        if not visited[cur_x][cur_y] and grids[cur_x][cur_y]==1:
            visited[cur_x][cur_y]=True
            dfs(grids, cur_x, cur_y)
    

# 读取输入值
n,m = map(int, input().split())
grids=[]
for i in range(n):
    grids.append(list(map(int, input().split())))
# 构造visited
visited = [[False]*m for _ in range(n)]

# 处理边界值
for i in range(m):
    if grids[0][i]==1 and not visited[0][i]:
        visited[0][i]=True
        dfs(grids,0,i)
    # 下边界
    if grids[n-1][i]==1 and not visited[n-1][i]:
        visited[n-1][i]=True
        dfs(grids,n-1,i)

# 处理左右边界
for j in range(n):
    if grids[j][0]==1 and not visited[j][0]:
        visited[j][0]=True
        dfs(grids,j, 0)
    if grids[j][m-1]==1 and not visited[j][m-1]:
        visited[j][m-1]=True
        dfs(grids,j, m-1)

# 计算孤岛面积
result = 0  # 重新对result初始化，避免遍历边界岛屿时的累加值
for i in range(n):
    for j in range(m):
        if grids[i][j]==1 and not visited[i][j]:
            visited[i][j]=True
            dfs(grids, i, j)
print(result)

# 深搜；邻接矩阵；解法：把边界岛屿变为2，剩下的1都是孤岛的，就好辨别了
# 这道题不用visited
directions=[[1,0],[-1,0],[0,1],[0,-1]]

def dfs(grids,x,y):
    grids[x][y]=2
    for i,j in directions:
        cur_x = x+i
        cur_y = y+j
        # 终止条件，超过边界
        if cur_x<0 or cur_x>=len(grids) or cur_y<0 or cur_y>=len(grids[0]):
            continue
        # 陆地
        if grids[cur_x][cur_y]==1:
            dfs(grids,cur_x,cur_y)

# 导入输入值
n,m = map(int, input().split())
grids = []
for i in range(n):
    grids.append(list(map(int, input().split())))

# 遍历左右边
for i in range(n):
    if grids[i][0]==1:
        dfs(grids, i, 0)
    if grids[i][m-1]==1:
        dfs(grids, i, m-1)
# 遍历上下边
for j in range(m):
    if grids[0][j]==1:
        dfs(grids,0,j)
    if grids[n-1][j]==1:
        dfs(grids,n-1,j)

# 现在边界岛屿值都变成2了，那重新遍历，遇到2为边缘岛屿，遇到1为孤岛
for i in range(n):
    for j in range(m):
        if grids[i][j]==2:   # 周边岛变回陆地
            grids[i][j]=1
        elif grids[i][j]==1:
            grids[i][j]=0   # 孤岛变成海洋
            
for row in grids:
    print(' '.join(map(str, row)))   # 打印邻接矩阵

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

def dfs(i,j,grids,visited,side):
    if visited[i][j]:
        return
    
    visited[i][j] = True
    side.add((i,j))
    
    for x,y in directions:
        cur_x = i+x
        cur_y = j+y
        if (
            0<=cur_x<len(grids)
            and 0<=cur_y<len(grids[0])
            and int(grids[cur_x][cur_y]>=int(grids[i][j])) # 怎么感觉是从低向高流呢？
            ):
                dfs(cur_x, cur_y, grids, visited, side)


# 导入输入值
n,m = map(int, input().split())
# 构造邻接矩阵
grids=[]
for i in range(n):
    grids.append(list(map(int, input().split())))

# 是否可达第一边界
visited = [[False]*m for _ in range(n)]
for i in range(m):
    dfs(0, i, grids, visited, first)
for i in range(n):
    dfs(i, 0, grids, visited, first)

# 是否可达第二边界
visited = [[False]*m for _ in range(n)]
for i in range(m):
    dfs(n-1, i, grids, visited, second)
for i in range(n):
    dfs(i, m-1, grids, visited, second)

res = first & second
for x,y in res:
    print(f"{x} {y}")

# 本题思路：统计每个岛屿的面积，从2开始（避开0，1）给岛屿编号[mark，area]；深搜；邻接矩阵
# 因为每个点都mark了，所以当值不为0也不为1时，代表以及访问过了，本题不用visited

import collections

directions = [[1,0],[-1,0],[0,1],[0,-1]]
count = 0

def dfs(grids,mark,x,y):
    global count

    # 终止条件，遇到海水或者已访问过的
    if grids[x][y] == 0 or grids[x][y] != 1:   # 因为
        return
    grids[x][y] = mark
    count += 1
    
    for i,j in directions:
        next_x = x+i
        next_y = y+j
        if (
            0<=next_x<len(grids)
            and 0<=next_y<len(grids[0])
            and grids[next_x][next_y] == 1
            ):
                dfs(grids,mark,next_x,next_y)
        # if next_x<0 or next_x>=len(grids) or next_y<0 or next_y>=len(grids[0]):
        #     continue
        # dfs(grids,mark,next_x,next_y)   # 不用判断是否遍历过，因为前面已经给出遍历条件

# 导入输入值
n,m = map(int, input().split())
grid = []
for i in range(n):
    grid.append(list(map(int, input().split())))



# 记录岛屿标记
gridNum = {}
mark=2

# # 判断是否整个矩阵都是陆地
# isAllgrid = True

# 第一次遍历地图：统计每个岛屿的面积
for i in range(n):
    for j in range(m):
        if grid[i][j]==1:
            count = 0
            dfs(grid,mark,i,j)
            gridNum[mark]=count
            mark += 1

# print(gridNum)
res = 0
# 第二次遍历地图：把每个海洋都变成陆地试一次
for i in range(n):
    for j in range(m):
        if grid[i][j]==0:
            max_island = 1
            v = set()
            for x,y in directions:
                next_x = x+i
                next_y = y+j
                if (
                    0<=next_x<len(grid) and 0<=next_y<len(grid[0])
                    and grid[next_x][next_y] != 0
                    and grid[next_x][next_y] not in v     # 避免重复
                ):
                    max_island += gridNum[grid[next_x][next_y]]
                    v.add(grid[next_x][next_y])
            res = max(res, max_island)

if res == 0: # 无水，全是陆地
    print(max(gridNum.values()))
else:
    print(res)

# 无向图；广搜；如果能到尾巴，一定是最短距离；如果两个字符串有两个字母一样，则两者间有连线

def judge(s1, s2):
    """???判断两个字符串有没有连线，即两者需要有两个一样的字母"""
    count = 0
    for i in range(len(s1)):
        if s1[i] != s2[i]:
            count += 1
    return count==1
    

# 导入输入值
n = map(int, input())
beginstr, endstr = input().split()

# 如果首尾一样，则直接连线，得最短路径
if beginstr == endstr:
    print(0)
else:
    # 导入剩下的输入值
    strlist = []
    for i in range(n):
        strlist.append(input())
        
    # 使用广搜
    visited = [False for _ in range(n)]
    # 构造一个队列
    queue = [[beginstr, 1]]  # 存字符串和路径长度
    while queue:
        str, step = queue.pop(0)
        if judge(str,endstr):
            print(step+1)
        else:
            for i in range(n):
                if visited[i]==False and judge(strlist[i], str):
                    visited[i] = True
                    queue.append([strlist[i], step+1])
    print(0)
    

def dfs(grids, key, visited):
    for neighbor in grids[key]:
        if not visited[neighbor]:
            visited[neighbor] = True
            dfs(grids, neighbor, visited)
            
# 输入值
n,k = map(int, input().split())
grids = [[] for _ in range(n+1)]

for _ in range(k):
    s, t = map(int, input().split())
    grids[s].append(t)

visited = [False]*(n+1)
visited[1] = True
dfs(grids,1,visited)

index = 0
for i in range(1, n+1):
    if not visited[i]:
        print(-1)
        index = 1
        break
if index == 0:
    print(1)
    

# 解法二：陆地数*4-相邻陆地数*2=边长

# 输入值
n,m = map(int, input().split())
grid = []
for i in range(n):
    grid.append(list(map(int, input().split())))

# 初始化陆地数和相邻陆地数
sum_land = 0
cross = 0

for i in range(n):
    for j in range(m):
        if grid[i][j] == 1:
            sum_land += 1
            if i-1 >= 0 and grid[i-1][j]==1:  # 上边相邻路径
                cross += 1
            if j-1>=0 and grid[i][j-1] == 1:  # 左边相邻路径
                cross += 1

result = sum_land*4 - cross*2
print(result)