【代码随想录算法训练营第五十九天|卡码网110.字符串接龙、105.有向图的完全可达性、106.岛屿的周长】

卡码网110.字符串接龙

这题是在字符串上进行广搜，字符串广搜是对一个字符串按照位置来搜索，与原字符串只有一个位置字符不同那么就是在原字符串的基础上距离加1。因此需要一个字典来记录每个字符串和beginStr的距离，然后创建一个队列，每次对队列第一个字符串进行广搜，找到匹配且没有访问过的字符串就加入队列尾部等待处理，并且在字典中令他的距离变成现在访问的字符串的距离+1，直到遇见和endStr匹配的字符串输出距离。因为广搜是距离从小到达搜索的，所以第一次遇到和endStr匹配的就一定是最小距离。

import re
import collections
def bfs(strings, beginStr, endStr):
    visited = {}
    for string in strings:
        visited[string] = 1
    visited[beginStr] = 1
    st = collections.deque([beginStr])
    while st:
        temp = st.popleft()
        path = visited[temp]
        for i in range(len(beginStr)):
            regex = re.compile(temp[:i]+'.'+temp[i+1:])
            if regex.fullmatch(endStr):
                return path+1
            for s in strings:
                if regex.fullmatch(s) and visited[s] == 1:
                    st.append(s)
                    visited[s] = path + 1
    return 0

if __name__ == '__main__':
    n = int(input())
    beginStr, endStr = input().split()
    strings = []
    for i in range(n):
        strings.append(input())
    print(bfs(strings, beginStr, endStr))

105.有向图的完全可达性

DFS去从1开始深度搜索，搜索到的结点标注，最后如果所有结点都标注了就输出1否则为-1。

def dfs(cur, pairs, visited):
    if visited[cur]==1:
        return 
    visited[cur] = 1
    for nextNode in pairs[cur]:
        dfs(nextNode, pairs, visited)

if __name__=='__main__':
    n, k = map(int, input().split())
    pairs = [[] for _ in range(n+1)]
    for i in range(k):
        a, b = map(int, input().split())
        pairs[a].append(b)
    visited = [0] * (n+1)
    dfs(1, pairs, visited)
    if sum(visited) == n:
        print(1)
    else:
        print(-1)

106.岛屿的周长

就是在之前岛屿相关题目的基础上变形，在dfs/bfs的时候，如果遇到岛屿在往下一个区域探到海洋，那就让周长+1，别的都一样。

def dfs(x, y, islands, visited, perimeter):
    visited[x][y] = True
    n = len(islands)
    m = len(islands[0])
    directions = [[1, 0], [-1, 0], [0, 1], [0, -1]]
    for d in directions:
        nextx = x + d[0]
        nexty = y + d[1]
        if nextx < 0 or nextx >= n or nexty < 0 or nexty >= m:
            perimeter += 1
            continue
        if islands[nextx][nexty] == 0:
            perimeter += 1
            continue
        if islands[nextx][nexty] == 1 and visited[nextx][nexty] == False:
            perimeter = dfs(nextx, nexty, islands, visited, perimeter)
    return perimeter
if __name__ == '__main__':
    n, m = map(int, input().split())
    islands = [[0] * m for _ in range(n)]
    for i in range(n):
        lands = input().split()
        for j in range(m):
            islands[i][j] = int(lands[j])
    visited = [[False] * m for _ in range(n)]
    for i in range(n):
        for j in range(m):
            if islands[i][j] == 1 and visited[i][j] == False:
                perimeter = dfs(i, j, islands, visited, 0)
    print(perimeter)