当前位置 博文首页 > wang785994599的博客:小岛问题最多可达点

    wang785994599的博客:小岛问题最多可达点

    作者:[db:作者] 时间:2021-09-06 18:58

    广度优先搜索,Python代码如下,搞清楚二维数组里的横纵坐标,这类题很简单:

    class Queue(object):
        def __init__(self):
            self.items = []
            self.head = 0
            self.tail = 0
        def append(self,node):
            self.items.append(node)
            self.tail += 1
        def get(self):
            return self.items[self.head]
    map_list = [
        [1,2,1,0,0,0,0,0,2,3],
        [3,0,2,0,1,2,1,0,1,2],
        [4,0,1,0,1,2,3,2,0,1],
        [3,2,0,0,0,1,2,4,0,0],
        [0,0,0,0,0,0,1,5,3,0],
        [0,1,2,1,0,1,5,4,3,0],
        [0,1,2,3,1,3,6,2,1,0],
        [0,0,3,4,8,9,7,5,0,0],
        [0,0,0,3,7,8,6,0,1,2],
        [0,0,0,0,0,0,0,0,1,0]
    ]
    x,y = 7,5
    next = [[0,1],[1,0],[0,-1],[-1,0]]
    #已达点
    book_list = []
    #初始化
    can_arrive = Queue()
    can_arrive.append((7,5))
    
    while can_arrive.head<can_arrive.tail: #到达最后一个节点
        #获得一个点,遍历该点可达点
        x,y = can_arrive.get()[0],can_arrive.get()[1]
        #正在遍历的该点,已经到达,放入到已达点列表
        book_list.append((x, y))
        #依次为前后左右
        for j in range(4):
            #下一点的横坐标
            tx = x + next[j][1]
            #下一点的纵坐标
            ty = y + next[j][0]
            #判定,越界?,已达?
            if 0<=tx<=9 and 0<=ty<=9 and (tx,ty) not in book_list:
                if map_list[tx][ty] != 0 and (tx,ty) not in can_arrive.items:
                    #将该点放到可达列表,准备遍历
                    can_arrive.append((tx,ty))
        #头指针后移
        can_arrive.head +=1
    
    if __name__ == '__main__':
        print(can_arrive.items)
    
    
    
    
    

    深度优先搜索代码:

    import sys
    sys.setrecursionlimit(100000)
    map_list = [
        [1,2,1,0,0,0,0,0,2,3],
        [3,0,2,0,1,2,1,0,1,2],
        [4,0,1,0,1,2,3,2,0,1],
        [3,2,0,0,0,1,2,4,0,0],
        [0,0,0,0,0,0,1,5,3,0],
        [0,1,2,1,0,1,5,4,3,0],
        [0,1,2,3,1,3,6,2,1,0],
        [0,0,3,4,8,9,7,5,0,0],
        [0,0,0,3,7,8,6,0,1,2],
        [0,0,0,0,0,0,0,0,1,0]
    ]
    next = [[0,1],[1,0],[0,-1],[-1,0]]
    #已达点
    book_list = []
    #初始化
    can_arrive = [(7,5)]
    def dfs(x,y):
        book_list.append((x, y))
        for i in range(4):
            tx = x + next[i][1]
            ty = y + next[i][0]
            #判定
            if 0<=tx<=9 and 0<=ty<=9 and (tx,ty) not in book_list:
                if map_list[tx][ty]!=0:
                    if (tx,ty) not in can_arrive:
                        can_arrive.append((tx,ty))
                    dfs(tx,ty)
        #book_list.remove((x,y))
    if __name__ == '__main__':
        dfs(7,5)
        print(can_arrive)
        print(len(can_arrive))

    ?

    cs
    下一篇:没有了