当前位置：首页 > article >正文

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

article 2025/3/1 12:16:33

110. 字符串接龙

#邻接表记录 只差一个元素的列表
from collections import deque

#判断两个字符串是不是只相差一个字符
def distinguish(str1,str2):
    if len(str1)!=len(str2):
        return False
    flag=0
    for i in range(len(str1)):
        if str1[i]!=str2[i]:
            flag+=1
    return flag<=1

def assemble(strList):
    dict={}
    for i in range(len(strList)):
        temp=[]
        for j in range(len(strList)):
            if i==j:
                continue
            if distinguish(strList[i],strList[j]):
                temp.append(strList[j])
        dict[strList[i]]=temp
    
    return dict
    
    
def main():
    n=int(input())
    beginStr,endStr=input().split()
    strList=[]
    for i in range(n):
        strList.append(input())
    strList.append(beginStr)
    strList.append(endStr)
    adList=assemble(strList)
    res=1
    #从起始的邻接开始广度遍历
    dq=deque()
    dq.append(beginStr)
    visited=set()
    visited.add(beginStr)
    while len(dq)>0:
        res+=1
        for i in range(len(dq)):
            tempStr=dq.popleft()
            tempList=adList[tempStr]
            for j in range(len(tempList)):
                if tempList[j]==endStr:
                    print(res)
                    return
                if tempList[j] not in visited:
                    dq.append(tempList[j])
                    visited.add(tempList[j])
        
    
    print(0)
    

if __name__=="__main__":
    main()

[105. 有向图的完全可达性

](https://kamacoder.com/problempage.php?pid=1177)
思路：bfs判断节点是否全部可达

from collections import defaultdict,deque

def main():
    n,k=map(int,input().split())
    dict=defaultdict(list)
    for i in range(k):
        s,t=map(int,input().split())
        dict[s].append(t)

    #把从1出发能到达的点都加入到visited中，判断大小是否为n
    dq=deque()
    dq.append(1)
    visited=set()
    visited.add(1)
    while len(dq)>0:
        temp=dq.popleft()
        tempList=dict[temp]
        for node in tempList:
            if node not in visited:
                dq.append(node)
                visited.add(node)
    res=1 if len(visited)==n else -1
    print(res)
        
        
        
if __name__=="__main__":
    main()

106. 岛屿的周长

#每个1的四边有0则周长加1 越界也加1

direction=[[-1,0],[1,0],[0,-1],[0,1]]
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:
                for d in direction:
                    x=i+d[0]
                    y=j+d[1]
                    if 0<=x<=n-1 and 0<=y<=m-1 :
                        if graph[x][y]==0:
                            res+=1
                    else:
                        res+=1
    print(res)                        
                        
if __name__=="__main__":
    main()