首页 > 求问华为的一道笔试题:连通湖泊的最小代价
头像
Google轰炸机
编辑于 2021-09-03 11:53
+ 关注

求问华为的一道笔试题:连通湖泊的最小代价

求问华为的一道笔试题:连通湖泊的最小代价。谢谢!
题目:给定一个二维矩阵,0代表湖泊,1,2代表陆地,也代表挖通这块陆地的代价。求使二维矩阵中所有湖泊连通所花费的最小挖地代价。
# 例1: 代价为1,挖通grid[1][1]即可
# [[0,1,1,0],[0,1,0,0],[0,1,0,0],[0,1,0,0],[0,1,0,1],[1,1,1,1]]
# [[0 1 1 0]
#  [0 1 0 0]
#  [0 1 0 0]
#  [0 1 0 0]
#  [0 1 0 1]
#  [1 1 1 1]]
# 例2: 代价为2,挖通grid[0][1]和grid[2][1]即可
# [[0, 1, 0, 1], [1, 0, 2, 0], [0, 1, 0, 0]]
# [[0 1 0 1]
#  [1 0 2 0]
#  [0 1 0 0]]
# 例3: 代价为4,挖通grid[0][1]和grid[0][2]即可
# [[0, 2, 2, 0]]# 思路:挑出所有陆地格子[(x0,y0),(x1,y1),...,(xn,yn)],和湖泊格子[(p0,q0),(p1,q1),...,(pn,qn)]。用dfs尝试修改其为湖泊grid[xi][yi]=0,记录修改过的个数holes。然后使用bfs查看是否连接了所有湖泊,若连接了所有湖泊,则肯定有bfs()-holes = len(lakes)。但最后程序没跑出来,可能进入死循环,或时间复杂度太高。

# 思路:挑出所有陆地格子[(x0,y0),(x1,y1),...,(xn,yn)],和湖泊格子[(p0,q0),(p1,q1),...,(pn,qn)]。用dfs尝试修改其为湖泊grid[xi][yi]=0,记录修改过的个数holes。然后使用bfs查看是否连接了所有湖泊,若连接了所有湖泊,则肯定有bfs()-holes = len(lakes)。但最后程序没跑出来,可能进入死循环,或时间复杂度太高。

# 已确认问题1:(可能没有处理湖泊数为0的情况)
# 已确认问题2:当维度太大(5*6),程序会跑不完

def bfs(x0, y0):
    from collections import deque
    q = deque()
    visited = set()
    head = (x0, y0)
    q.append(head)
    visited.add(head)
    cnt = 1
    while q:
        x, y = q.popleft()
        neighbors = ((x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1))
        for nei in neighbors:
            nx, ny = nei[0], nei[1]
            if 0 <= nx < m and 0 <= ny < n and grid[nx][ny] == 0 and nei not in visited:
                cnt += 1
                q.append(nei)
                visited.add(nei)
    return cnt

def dfs(k, path_sum, holes):
    if bfs(lakes[0][0], lakes[0][1]) - holes == len(lakes):
        minn[0] = min(minn[0], path_sum)
        return
    if k == len(lands):
        return
    # 不挖
    dfs(k + 1, path_sum, holes)
    # 挖
    i, j = lands[k]
    path_sum += grid[i][j]
    holes += 1
    temp = grid[i][j]
    grid[i][j] = 0
    dfs(k + 1, path_sum, holes)
    path_sum -= temp
    holes -= 1
    grid[i][j] = temp


grid = [[0, 2, 2, 0]]
m, n = len(grid), len(grid[0])
lands = []
lakes = []
for i in range(m):
    for j in range(n):
        if grid[i][j] == 0:
            lakes.append((i, j))
        else:
            lands.append((i, j))

minn = [m * n]
dfs(0, 0, 0)
print(minn[0]) 

全部评论

(1) 回帖
加载中...
话题 回帖

相关热帖

近期热帖

历年真题 真题热练榜 24小时
技术(软件)/信息技术类
查看全部

近期精华帖

热门推荐