给定一个二维二进制矩阵，我们需要找到由 1 组成的最大区域的面积。这些 1 之间可以是水平、垂直或对角线方向连接的。
示例：
> 输入: M[][]= {{1, 0, 0, 0, 1, 0, 0},
> {0, 1, 0, 0, 1, 1, 0},
> {1, 1, 0, 0, 0, 0, 0},
> {1, 0, 0, 1, 1, 0, 0},
> {1, 0, 0, 1, 0, 1, 1}}
>
> 输出: 6
> 解释: 图中红色标记的区域具有最大的面积，包含 6 个单元格。
> !Max-Area-of-Island最大区域面积为 6
> 输入: M[][] = {{0, 0, 1, 1, 0},
> {1, 0, 1, 1, 0},
> {0, 1, 0, 0, 0},
> {0, 0, 0, 0, 1}}
> 输出: 6
> 解释: 在下面的示例中，有 2 个区域。一个面积为 1，另一个面积为 6。因此，最大面积为 6。
目录
- 使用 DFS – O(rows cols) 时间复杂度和 O(rows cols) 空间复杂度
- 使用 BFS – O(rows * cols) 时间复杂度和 O(rows + cols) 空间复杂度
使用 DFS – O(rows cols) 时间复杂度和 O(rows cols) 空间复杂度
> 这个思路的核心是遍历输入矩阵，如果某个单元格的值为 1，我们就从该单元开始运行 DFS 算法，以访问该连通分量中的所有单元格。在 DFS 过程中，我们需要跟踪当前区域的面积，并对所有八个方向的邻居进行递归调用。此外，在访问任何单元格时，我们将其值更新为 0 以标记它已被访问过。这样，通过直接修改输入矩阵来标记已访问的单元格，我们可以避免维护一个额外的二维矩阵来存储访问状态。
下面是上述方法的实现：
C++
CODEBLOCK_1f6ead95
C
// C Program to find area of the largest region of 1s
#include
#include
// Define constants for rows and columns
#define ROWS 5
#define COLS 7
// A function to check if cell(r, c) can be included in DFS
int isSafe(int M[ROWS][COLS], int r, int c, int rows, int cols) {
// Row number is in range, column number is in range,
// and value is 1
return (r >= 0 && r = 0 && c < cols)
&& (M[r][c] == 1);
}
// Depth-First-Search to visit all cells in the current island
void DFS(int M[ROWS][COLS], int r, int c, int rows, int cols, int *area) {
// These arrays are used to get row and column numbers of 8
// neighbours of a given cell
int dirR[] = {-1, -1, -1, 0, 0, 1, 1, 1};
int dirC[] = {