岛屿的最大面积leetcode

Question

有个n×m的花园，'#'是土地，'.'是溪水，【种花面积】是由一些相邻的’#‘组合构成，这里的「相邻」要求两个’#‘必须在水平或者竖直的四个方向上相邻。我们把上下左右四个方向相邻的’#'连通区域作为一块种花面积，现在需要统计最大的一块面积是多少？如果不存在连通块，输出-1。要求：使用广搜。暴力破解

Answer 1

引自免费微信小程序：皆我百晓生

要解决这个问题，我们可以使用广度优先搜索（BFS）算法来遍历整个花园地图，寻找最大种花面积。下面是一个详细的步骤分解以及相应的Python代码实现。

步骤分解：

1. 初始化：创建一个二维数组garden来表示花园的状态。同时，定义一个队列queue用于存储待探索的点，以及一个变量max_area来记录最大的种花面积。
2. 遍历花园：从左到右、从上到下遍历花园的每一个位置。对于每个位置，检查是否为土地（'#'），如果是，则从这个位置开始进行广度优先搜索。
3. 广度优先搜索：将当前位置加入队列，并将其标记为已访问（可以将它变为另一个字符，比如'X'）。然后开始循环处理队列中的元素，每次从队列中取出一个元素，检查其四周的邻居是否也是土地，如果是，将它们也加入队列并标记为已访问。同时，计算当前连通块的面积。
4. 更新最大面积：每完成一个连通块的搜索，就用当前连通块的面积更新max_area。
5. 返回结果：遍历结束后，max_area即为所求的最大种花面积。如果max_area仍然为初始值（例如0），则说明没有找到任何连通的土地，应返回-1。

Python代码实现：

from collections import deque

def max_flower_area(garden):
    if not garden or not garden[0]:
        return -1
    
    rows, cols = len(garden), len(garden[0])
    max_area = 0
    directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]  # 右下左上

    def bfs(r, c):
        area = 1
        queue = deque([(r, c)])
        garden[r][c] = 'X'  # 标记为已访问
        
        while queue:
            x, y = queue.popleft()
            for dx, dy in directions:
                nx, ny = x + dx, y + dy
                if 0 <= nx < rows and 0 <= ny < cols and garden[nx][ny] == '#':
                    garden[nx][ny] = 'X'
                    queue.append((nx, ny))
                    area += 1
        return area

    for r in range(rows):
        for c in range(cols):
            if garden[r][c] == '#':
                max_area = max(max_area, bfs(r, c))

    return max_area if max_area > 0 else -1

# 示例输入
garden = [
    ['#', '.', '#', '#', '.'],
    ['#', '.', '.', '.', '#'],
    ['#', '#', '#', '.', '.'],
    ['.', '.', '.', '.', '.']
]

print(max_flower_area(garden))  # 输出应为9，因为最大的连通土地面积为9

这段代码首先导入了deque类，这是为了高效地实现队列操作。然后定义了max_flower_area函数，该函数接受一个二维数组garden作为参数。通过遍历和广度优先搜索，最终返回花园中最大的种花面积。如果花园中没有任何土地，函数将返回-1。