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

# 例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])