当前位置 博文首页 > wang785994599的博客:小岛问题最多可达点
广度优先搜索,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