200. Number of Islands
給定一個 m x n 的二維二進制網格 grid，該網格表示由 '1'（陸地）和 '0'（水）組成的地圖，返回島嶼的數量。
一個島嶼被水包圍，通過水平或垂直連接的陸地形成。你可以假設網格的所有四個邊都被水包圍。
範例：
輸入：
grid =
[ ["1","1","1","1","0"],
["1","1","0","1","0"],
["1","1","0","0","0"],
["0","0","0","0","0"]
]
輸出：
輸出：
1
解析：
在這個示例中，整個地圖中只有一個島嶼，它包含所有相連的 '1'。
Python
from typing import List
class Solution:
def numIslands(self, grid: List[List[str]]) -> int:
if not grid:
return 0
def dfs(grid, i, j):
# Check for boundary conditions and if the current cell is '0' or already visited
if i < 0 or i >= len(grid) or j < 0 or j >= len(grid[0]) or grid[i][j] == '0':
return
# Mark the cell as visited by setting it to '0'
grid[i][j] = '0'
# Visit all adjacent cells (up, down, left, right)
dfs(grid, i + 1, j)
dfs(grid, i - 1, j)
dfs(grid, i, j + 1)
dfs(grid, i, j - 1)
num_islands = 0
for i in range(len(grid)):
for j in range(len(grid[0])):
if grid[i][j] == '1':
num_islands += 1
dfs(grid, i, j)
return num_islands
18.94MB, 235ms
C++
#include <vector>
using namespace std;
class Solution {
public:
int numIslands(vector<vector<char>>& grid) {
if (grid.empty()) {
return 0;
}
int num_islands = 0;
int rows = grid.size();
int cols = grid[0].size();
for (int i = 0; i < rows; ++i) {
for (int j = 0; j < cols; ++j) {
if (grid[i][j] == '1') {
++num_islands;
dfs(grid, i, j);
}
}
}
return num_islands;
}
private:
void dfs(vector<vector<char>>& grid, int i, int j) {
// Check for boundary conditions and if the current cell is '0' or already visited
if (i < 0 || i >= grid.size() || j < 0 || j >= grid[0].size() || grid[i][j] == '0') {
return;
}
// Mark the cell as visited by setting it to '0'
grid[i][j] = '0';
// Visit all adjacent cells (up, down, left, right)
dfs(grid, i + 1, j);
dfs(grid, i - 1, j);
dfs(grid, i, j + 1);
dfs(grid, i, j - 1);
}
};
16.10MB, 22ms
Javascript
/**
* @param {character[][]} grid
* @return {number}
*/
var numIslands = function(grid) {
if (!grid || grid.length === 0) {
return 0;
}
const rows = grid.length;
const cols = grid[0].length;
let numIslands = 0;
const dfs = (grid, i, j) => {
// Check for boundary conditions and if the current cell is '0' or already visited
if (i < 0 || i >= rows || j < 0 || j >= cols || grid[i][j] === '0') {
return;
}
// Mark the cell as visited by setting it to '0'
grid[i][j] = '0';
// Visit all adjacent cells (up, down, left, right)
dfs(grid, i + 1, j);
dfs(grid, i - 1, j);
dfs(grid, i, j + 1);
dfs(grid, i, j - 1);
};
for (let i = 0; i < rows; i++) {
for (let j = 0; j < cols; j++) {
if (grid[i][j] === '1') {
numIslands++;
dfs(grid, i, j);
}
}
}
return numIslands;
};
51.72MB, 70ms
