当前位置: 面试刷题>> 大岛的数量 (经典算法题500道)


题目描述补充

给定一个二维网格(grid),其中每个单元格可以是陆地(用 '1' 表示)或水域(用 '0' 表示)。网格中的陆地由水平或垂直四个方向上相连的 '1' 组成。现在,我们需要计算网格中独立岛屿(即被水域完全包围的陆地区域,且陆地之间不相互连接)的数量。

示例

给定网格:

1 1 0 0 0
1 1 0 0 0
0 0 1 0 0
0 0 0 1 1

返回岛屿的数量为 3。

PHP 代码示例

function numIslands($grid) {
    if (empty($grid)) {
        return 0;
    }

    $rows = count($grid);
    $cols = count($grid[0]);
    $count = 0;

    for ($i = 0; $i < $rows; $i++) {
        for ($j = 0; $j < $cols; $j++) {
            if ($grid[$i][$j] == '1') {
                dfs($grid, $i, $j);
                $count++;
            }
        }
    }

    return $count;
}

function dfs(&$grid, $i, $j) {
    $rows = count($grid);
    $cols = count($grid[0]);

    if ($i < 0 || $j < 0 || $i >= $rows || $j >= $cols || $grid[$i][$j] != '1') {
        return;
    }

    $grid[$i][$j] = '0'; // 标记为已访问

    dfs($grid, $i - 1, $j); // 上
    dfs($grid, $i + 1, $j); // 下
    dfs($grid, $i, $j - 1); // 左
    dfs($grid, $i, $j + 1); // 右
}

// 使用示例
$grid = [
    ['1', '1', '0', '0', '0'],
    ['1', '1', '0', '0', '0'],
    ['0', '0', '1', '0', '0'],
    ['0', '0', '0', '1', '1']
];
echo numIslands($grid); // 输出: 3

// 码小课网站中有更多相关内容分享给大家学习

Python 代码示例

def numIslands(grid):
    if not grid:
        return 0

    rows, cols = len(grid), len(grid[0])
    count = 0

    for i in range(rows):
        for j in range(cols):
            if grid[i][j] == '1':
                dfs(grid, i, j)
                count += 1

    return count

def dfs(grid, i, j):
    rows, cols = len(grid), len(grid[0])

    if i < 0 or j < 0 or i >= rows or j >= cols or grid[i][j] != '1':
        return

    grid[i][j] = '0' # 标记为已访问

    dfs(grid, i - 1, j) # 上
    dfs(grid, i + 1, j) # 下
    dfs(grid, i, j - 1) # 左
    dfs(grid, i, j + 1) # 右

# 使用示例
grid = [
    ['1', '1', '0', '0', '0'],
    ['1', '1', '0', '0', '0'],
    ['0', '0', '1', '0', '0'],
    ['0', '0', '0', '1', '1']
]
print(numIslands(grid)) # 输出: 3

# 码小课网站中有更多相关内容分享给大家学习

JavaScript 代码示例

function numIslands(grid) {
    if (!grid.length) {
        return 0;
    }

    const rows = grid.length;
    const cols = grid[0].length;
    let count = 0;

    for (let i = 0; i < rows; i++) {
        for (let j = 0; j < cols; j++) {
            if (grid[i][j] === '1') {
                dfs(grid, i, j);
                count++;
            }
        }
    }

    return count;
}

function dfs(grid, i, j) {
    const rows = grid.length;
    const cols = grid[0].length;

    if (i < 0 || j < 0 || i >= rows || j >= cols || grid[i][j] !== '1') {
        return;
    }

    grid[i][j] = '0'; // 标记为已访问

    dfs(grid, i - 1, j); // 上
    dfs(grid, i + 1, j); // 下
    dfs(grid, i, j - 1); // 左
    dfs(grid, i, j + 1); // 右
}

// 使用示例
const grid = [
    ['1', '1', '0', '0', '0'],
    ['1', '1', '0', '0', '0'],
    ['0', '0', '1', '0', '0'],
    ['0', '0', '0', '1', '1']
];
console.log(numIslands(grid)); // 输出: 3

// 码小课网站中有更多相关内容分享给大家学习
推荐面试题