难度中等
题目描述
给你一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。
岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。
此外，你可以假设该网格的四条边均被水包围。
示例 1：
输入：grid = [
['1','1','1','1','0'],
['1','1','0','1','0'],
['1','1','0','0','0'],
['0','0','0','0','0']
]
输出：1
示例 2：
输入：grid = [
['1','1','0','0','0'],
['1','1','0','0','0'],
['0','0','1','0','0'],
['0','0','0','1','1']
]
输出：3
提示：
m == grid.lengthn == grid[i].length1 <= m, n <= 300grid[i][j] 的值为 '0' 或 '1'
解法
方法一：DFS
思考
若将网格中每个值为 \(1\) 的格子单独计为一座岛，则四连通的陆地会被重复计数。 \(m,n \le 300\)，整图遍历可行，但须在同一次搜索中把同一连通块全部消掉。
注意到上下左右相邻的陆地构成一个连通分量，从任一尚未访问的陆地出发即可覆盖整座岛。为此扫描每个格子，遇到 \(1\) 便启动 DFS，沿途把陆地改写为 \(0\)，每启动一次搜索将答案加一。
我们可以使用深度优先搜索（DFS）来遍历每个岛屿。遍历网格中的每个单元格 \((i, j)\)，如果该单元格的值为 '1'，则说明我们找到了一个新的岛屿。我们可以从该单元格开始进行 DFS，将与之相连的所有陆地单元格的值都标记为 '0'，以避免重复计数。每次找到一个新的岛屿时，我们将岛屿数量加 1。
时间复杂度 \(O(m \times n)\)，空间复杂度 \(O(m \times n)\)。其中 \(m\) 和 \(n\) 分别为网格的行数和列数。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18 | class Solution:
def numIslands(self, grid: List[List[str]]) -> int:
def dfs(i, j):
grid[i][j] = '0'
for a, b in pairwise(dirs):
x, y = i + a, j + b
if 0 <= x < m and 0 <= y < n and grid[x][y] == '1':
dfs(x, y)
ans = 0
dirs = (-1, 0, 1, 0, -1)
m, n = len(grid), len(grid[0])
for i in range(m):
for j in range(n):
if grid[i][j] == '1':
dfs(i, j)
ans += 1
return ans
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33 | class Solution {
private char[][] grid;
private int m;
private int n;
public int numIslands(char[][] grid) {
m = grid.length;
n = grid[0].length;
this.grid = grid;
int ans = 0;
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if (grid[i][j] == '1') {
dfs(i, j);
++ans;
}
}
}
return ans;
}
private void dfs(int i, int j) {
grid[i][j] = '0';
int[] dirs = {-1, 0, 1, 0, -1};
for (int k = 0; k < 4; ++k) {
int x = i + dirs[k];
int y = j + dirs[k + 1];
if (x >= 0 && x < m && y >= 0 && y < n && grid[x][y] == '1') {
dfs(x, y);
}
}
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27 | class Solution {
public:
int numIslands(vector<vector<char>>& grid) {
int m = grid.size();
int n = grid[0].size();
int ans = 0;
int dirs[5] = {-1, 0, 1, 0, -1};
auto dfs = [&](this auto&& dfs, int i, int j) -> void {
grid[i][j] = '0';
for (int k = 0; k < 4; ++k) {
int x = i + dirs[k], y = j + dirs[k + 1];
if (x >= 0 && x < grid.size() && y >= 0 && y < grid[0].size() && grid[x][y] == '1') {
dfs(x, y);
}
}
};
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if (grid[i][j] == '1') {
dfs(i, j);
++ans;
}
}
}
return ans;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24 | func numIslands(grid [][]byte) int {
m, n := len(grid), len(grid[0])
var dfs func(i, j int)
dfs = func(i, j int) {
grid[i][j] = '0'
dirs := []int{-1, 0, 1, 0, -1}
for k := 0; k < 4; k++ {
x, y := i+dirs[k], j+dirs[k+1]
if x >= 0 && x < m && y >= 0 && y < n && grid[x][y] == '1' {
dfs(x, y)
}
}
}
ans := 0
for i := 0; i < m; i++ {
for j := 0; j < n; j++ {
if grid[i][j] == '1' {
dfs(i, j)
ans++
}
}
}
return ans
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28 | function numIslands(grid: string[][]): number {
const m = grid.length;
const n = grid[0].length;
let ans = 0;
const dirs = [-1, 0, 1, 0, -1];
const dfs = (i: number, j: number) => {
grid[i][j] = '0';
for (let k = 0; k < 4; ++k) {
const x = i + dirs[k];
const y = j + dirs[k + 1];
if (grid[x]?.[y] === '1') {
dfs(x, y);
}
}
};
for (let i = 0; i < m; ++i) {
for (let j = 0; j < n; ++j) {
if (grid[i][j] === '1') {
dfs(i, j);
ans++;
}
}
}
return ans;
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33 | const DIRS: [i32; 5] = [-1, 0, 1, 0, -1];
impl Solution {
pub fn num_islands(grid: Vec<Vec<char>>) -> i32 {
fn dfs(grid: &mut Vec<Vec<char>>, i: usize, j: usize) {
grid[i][j] = '0';
for k in 0..4 {
let x = (i as i32) + DIRS[k];
let y = (j as i32) + DIRS[k + 1];
if x >= 0
&& (x as usize) < grid.len()
&& y >= 0
&& (y as usize) < grid[0].len()
&& grid[x as usize][y as usize] == '1'
{
dfs(grid, x as usize, y as usize);
}
}
}
let mut grid = grid;
let mut ans = 0;
for i in 0..grid.len() {
for j in 0..grid[0].len() {
if grid[i][j] == '1' {
dfs(&mut grid, i, j);
ans += 1;
}
}
}
ans
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32 | public class Solution {
public int NumIslands(char[][] grid) {
int m = grid.Length;
int n = grid[0].Length;
int ans = 0;
int[] dirs = { -1, 0, 1, 0, -1 };
void Dfs(int i, int j) {
grid[i][j] = '0';
for (int k = 0; k < 4; ++k) {
int x = i + dirs[k];
int y = j + dirs[k + 1];
if (x >= 0 && x < m &&
y >= 0 && y < n &&
grid[x][y] == '1') {
Dfs(x, y);
}
}
}
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if (grid[i][j] == '1') {
Dfs(i, j);
ans++;
}
}
}
return ans;
}
}
|
方法二：BFS
思考
方法一已经用显式栈按连通分量抹掉陆地。同一四连通定义下，也可以用队列按层扩展邻接陆地，同样一次抹掉一座岛。
扫描顺序与方法一相同，空间仍由队列规模决定。
我们也可以使用广度优先搜索（BFS）来遍历每个岛屿。遍历网格中的每个单元格 \((i, j)\)，如果该单元格的值为 '1'，则说明我们找到了一个新的岛屿。我们可以从该单元格开始进行 BFS，将与之相连的所有陆地单元格的值都标记为 '0'，以避免重复计数。每次找到一个新的岛屿时，我们将岛屿数量加 1。
BFS 的具体过程如下：
- 将起始单元格 \((i, j)\) 入队，并将其值标记为 '0'。
- 当队列不为空时，执行以下操作：
- 出队一个单元格 \(p\)。
- 遍历 \(p\) 的四个相邻单元格 \((x, y)\)，如果 \((x, y)\) 在网格范围内且值为 '1'，则将其入队并将其值标记为 '0'。
时间复杂度 \(O(m \times n)\)，空间复杂度 \(O(m \times n)\)。其中 \(m\) 和 \(n\) 分别为网格的行数和列数。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22 | class Solution:
def numIslands(self, grid: List[List[str]]) -> int:
def bfs(i, j):
grid[i][j] = '0'
q = deque([(i, j)])
while q:
i, j = q.popleft()
for a, b in pairwise(dirs):
x, y = i + a, j + b
if 0 <= x < m and 0 <= y < n and grid[x][y] == '1':
q.append((x, y))
grid[x][y] = 0
ans = 0
dirs = (-1, 0, 1, 0, -1)
m, n = len(grid), len(grid[0])
for i in range(m):
for j in range(n):
if grid[i][j] == '1':
bfs(i, j)
ans += 1
return ans
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39 | class Solution {
private char[][] grid;
private int m;
private int n;
public int numIslands(char[][] grid) {
m = grid.length;
n = grid[0].length;
this.grid = grid;
int ans = 0;
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if (grid[i][j] == '1') {
bfs(i, j);
++ans;
}
}
}
return ans;
}
private void bfs(int i, int j) {
grid[i][j] = '0';
Deque<int[]> q = new ArrayDeque<>();
q.offer(new int[] {i, j});
int[] dirs = {-1, 0, 1, 0, -1};
while (!q.isEmpty()) {
int[] p = q.poll();
for (int k = 0; k < 4; ++k) {
int x = p[0] + dirs[k];
int y = p[1] + dirs[k + 1];
if (x >= 0 && x < m && y >= 0 && y < n && grid[x][y] == '1') {
q.offer(new int[] {x, y});
grid[x][y] = '0';
}
}
}
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35 | class Solution {
public:
int numIslands(vector<vector<char>>& grid) {
int m = grid.size();
int n = grid[0].size();
int ans = 0;
int dirs[5] = {-1, 0, 1, 0, -1};
auto bfs = [&](int i, int j) -> void {
grid[i][j] = '0';
queue<pair<int, int>> q;
q.push({i, j});
while (!q.empty()) {
auto [a, b] = q.front();
q.pop();
for (int k = 0; k < 4; ++k) {
int x = a + dirs[k];
int y = b + dirs[k + 1];
if (x >= 0 && x < grid.size() && y >= 0 && y < grid[0].size() && grid[x][y] == '1') {
q.push({x, y});
grid[x][y] = '0';
}
}
}
};
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if (grid[i][j] == '1') {
bfs(i, j);
++ans;
}
}
}
return ans;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29 | func numIslands(grid [][]byte) int {
m, n := len(grid), len(grid[0])
bfs := func(i, j int) {
grid[i][j] = '0'
q := [][]int{[]int{i, j}}
dirs := []int{-1, 0, 1, 0, -1}
for len(q) > 0 {
p := q[0]
q = q[1:]
for k := 0; k < 4; k++ {
x, y := p[0]+dirs[k], p[1]+dirs[k+1]
if x >= 0 && x < m && y >= 0 && y < n && grid[x][y] == '1' {
q = append(q, []int{x, y})
grid[x][y] = '0'
}
}
}
}
ans := 0
for i := 0; i < m; i++ {
for j := 0; j < n; j++ {
if grid[i][j] == '1' {
bfs(i, j)
ans++
}
}
}
return ans
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29 | function numIslands(grid: string[][]): number {
const m = grid.length;
const n = grid[0].length;
let ans = 0;
const bfs = (i: number, j: number) => {
grid[i][j] = '0';
const q = [[i, j]];
const dirs = [-1, 0, 1, 0, -1];
for (const [i, j] of q) {
for (let k = 0; k < 4; ++k) {
const x = i + dirs[k];
const y = j + dirs[k + 1];
if (grid[x]?.[y] == '1') {
q.push([x, y]);
grid[x][y] = '0';
}
}
}
};
for (let i = 0; i < m; ++i) {
for (let j = 0; j < n; ++j) {
if (grid[i][j] == '1') {
bfs(i, j);
++ans;
}
}
}
return ans;
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40 | use std::collections::VecDeque;
const DIRS: [i32; 5] = [-1, 0, 1, 0, -1];
impl Solution {
pub fn num_islands(grid: Vec<Vec<char>>) -> i32 {
fn bfs(grid: &mut Vec<Vec<char>>, i: usize, j: usize) {
grid[i][j] = '0';
let mut queue = VecDeque::from([(i, j)]);
while !queue.is_empty() {
let (i, j) = queue.pop_front().unwrap();
for k in 0..4 {
let x = (i as i32) + DIRS[k];
let y = (j as i32) + DIRS[k + 1];
if x >= 0
&& (x as usize) < grid.len()
&& y >= 0
&& (y as usize) < grid[0].len()
&& grid[x as usize][y as usize] == '1'
{
grid[x as usize][y as usize] = '0';
queue.push_back((x as usize, y as usize));
}
}
}
}
let mut grid = grid;
let mut ans = 0;
for i in 0..grid.len() {
for j in 0..grid[0].len() {
if grid[i][j] == '1' {
bfs(&mut grid, i, j);
ans += 1;
}
}
}
ans
}
}
|
方法三： 并查集
思考
若希望把“相邻即同一座岛”显式建成集合，则可将每块陆地视作并查集结点，与四邻中的陆地合并。
扫描结束后，岛屿数等于连通分量个数。合并与查询均可在近似线性时间内完成，空间仍为网格规模。
我们可以使用并查集（Union-Find）来解决这个问题。遍历网格中的每个单元格 \((i, j)\)，如果该单元格的值为 '1'，则将其与相邻的陆地单元格进行合并。最后，我们统计并查集中不同根节点的数量，即为岛屿的数量。
时间复杂度 \(O(m \times n \times \log (m \times n))\)，空间复杂度 \(O(m \times n)\)。其中 \(m\) 和 \(n\) 分别为网格的行数和列数。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22 | class Solution:
def numIslands(self, grid: List[List[str]]) -> int:
def find(x):
if p[x] != x:
p[x] = find(p[x])
return p[x]
dirs = (0, 1, 0)
m, n = len(grid), len(grid[0])
p = list(range(m * n))
for i in range(m):
for j in range(n):
if grid[i][j] == '1':
for a, b in pairwise(dirs):
x, y = i + a, j + b
if x < m and y < n and grid[x][y] == '1':
p[find(i * n + j)] = find(x * n + y)
return sum(
grid[i][j] == '1' and i * n + j == find(i * n + j)
for i in range(m)
for j in range(n)
)
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42 | class Solution {
private int[] p;
public int numIslands(char[][] grid) {
int m = grid.length;
int n = grid[0].length;
p = new int[m * n];
for (int i = 0; i < p.length; ++i) {
p[i] = i;
}
int[] dirs = {1, 0, 1};
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if (grid[i][j] == '1') {
for (int k = 0; k < 2; ++k) {
int x = i + dirs[k];
int y = j + dirs[k + 1];
if (x < m && y < n && grid[x][y] == '1') {
p[find(x * n + y)] = find(i * n + j);
}
}
}
}
}
int ans = 0;
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if (grid[i][j] == '1' && i * n + j == find(i * n + j)) {
++ans;
}
}
}
return ans;
}
private int find(int x) {
if (p[x] != x) {
p[x] = find(p[x]);
}
return p[x];
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36 | class Solution {
public:
int numIslands(vector<vector<char>>& grid) {
int m = grid.size();
int n = grid[0].size();
vector<int> p(m * n);
iota(p.begin(), p.end(), 0);
function<int(int)> find = [&](int x) -> int {
if (p[x] != x) {
p[x] = find(p[x]);
}
return p[x];
};
int dirs[3] = {1, 0, 1};
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if (grid[i][j] == '1') {
for (int k = 0; k < 2; ++k) {
int x = i + dirs[k];
int y = j + dirs[k + 1];
if (x < m && y < n && grid[x][y] == '1') {
p[find(x * n + y)] = find(i * n + j);
}
}
}
}
}
int ans = 0;
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
ans += grid[i][j] == '1' && i * n + j == find(i * n + j);
}
}
return ans;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36 | func numIslands(grid [][]byte) int {
m, n := len(grid), len(grid[0])
p := make([]int, m*n)
for i := range p {
p[i] = i
}
var find func(x int) int
find = func(x int) int {
if p[x] != x {
p[x] = find(p[x])
}
return p[x]
}
dirs := []int{1, 0, 1}
for i := 0; i < m; i++ {
for j := 0; j < n; j++ {
if grid[i][j] == '1' {
for k := 0; k < 2; k++ {
x, y := i+dirs[k], j+dirs[k+1]
if x < m && y < n && grid[x][y] == '1' {
p[find(x*n+y)] = find(i*n + j)
}
}
}
}
}
ans := 0
for i := 0; i < m; i++ {
for j := 0; j < n; j++ {
if grid[i][j] == '1' && i*n+j == find(i*n+j) {
ans++
}
}
}
return ans
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34 | function numIslands(grid: string[][]): number {
const m = grid.length;
const n = grid[0].length;
const p: number[] = Array.from({ length: m * n }, (_, i) => i);
function find(x: number): number {
if (p[x] != x) {
p[x] = find(p[x]);
}
return p[x];
}
const dirs = [1, 0, 1];
for (let i = 0; i < m; ++i) {
for (let j = 0; j < n; ++j) {
if (grid[i][j] == '1') {
for (let k = 0; k < 2; ++k) {
const x = i + dirs[k];
const y = j + dirs[k + 1];
if (grid[x]?.[y] == '1') {
p[find(i * n + j)] = find(x * n + y);
}
}
}
}
}
let ans = 0;
for (let i = 0; i < m; ++i) {
for (let j = 0; j < n; ++j) {
if (grid[i][j] == '1' && i * n + j == find(i * n + j)) {
++ans;
}
}
}
return ans;
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42 | const DIRS: [usize; 3] = [1, 0, 1];
impl Solution {
pub fn num_islands(grid: Vec<Vec<char>>) -> i32 {
let m = grid.len();
let n = grid[0].len();
let mut p: Vec<i32> = (0..(m * n) as i32).collect();
fn find(p: &mut Vec<i32>, x: usize) -> i32 {
if p[x] != (x as i32) {
p[x] = find(p, p[x] as usize);
}
p[x]
}
for i in 0..m {
for j in 0..n {
if grid[i][j] == '1' {
for k in 0..2 {
let x = i + DIRS[k];
let y = j + DIRS[k + 1];
if x < m && y < n && grid[x][y] == '1' {
let f1 = find(&mut p, x * n + y);
let f2 = find(&mut p, i * n + j);
p[f1 as usize] = f2;
}
}
}
}
}
let mut ans = 0;
for i in 0..m {
for j in 0..n {
if grid[i][j] == '1' && p[i * n + j] == ((i * n + j) as i32) {
ans += 1;
}
}
}
ans
}
}
|
方法四：显式栈
思考
若将每个值为 \(1\) 的格子单独计为一座岛，四连通的陆地会被重复计数。 \(m,n\le 300\)，一次扫描即可，但同一连通块必须在一次搜索里全部改成 \(0\)。
从一块陆地递归走向下一个邻居时，一条 \(1000\) 格的蛇形岛就会超出递归上限，而 \(300\times 300\) 的网格容得下这条蛇。
抹掉一座岛不需要递归返回值，只需要把四连通的 \(1\) 改成 \(0\)。
因此遇到 \(1\) 就把它压入显式栈。弹出后把四个方向上仍为 \(1\) 的邻居标成 \(0\) 并入栈，每启动一次搜索将答案加一。
扫描每个格子，遇到 '1' 就用显式栈淹没整座岛，沿途把陆地改成 '0'，并将答案加 \(1\)。
时间复杂度 \(O(m \times n)\)，空间复杂度 \(O(m \times n)\)。其中 \(m\) 和 \(n\) 分别为网格的行数和列数。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22 | class Solution:
def numIslands(self, grid: List[List[str]]) -> int:
def flood(i: int, j: int):
stk = [(i, j)]
grid[i][j] = '0'
while stk:
i, j = stk.pop()
for a, b in pairwise(dirs):
x, y = i + a, j + b
if 0 <= x < m and 0 <= y < n and grid[x][y] == '1':
grid[x][y] = '0'
stk.append((x, y))
ans = 0
dirs = (-1, 0, 1, 0, -1)
m, n = len(grid), len(grid[0])
for i in range(m):
for j in range(n):
if grid[i][j] == '1':
flood(i, j)
ans += 1
return ans
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31 | class Solution {
public int numIslands(char[][] grid) {
int m = grid.length;
int n = grid[0].length;
int ans = 0;
int[] dirs = {-1, 0, 1, 0, -1};
Deque<int[]> stk = new ArrayDeque<>();
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if (grid[i][j] == '1') {
grid[i][j] = '0';
stk.push(new int[] {i, j});
while (!stk.isEmpty()) {
int[] cur = stk.pop();
int a = cur[0], b = cur[1];
for (int k = 0; k < 4; ++k) {
int x = a + dirs[k];
int y = b + dirs[k + 1];
if (x >= 0 && x < m && y >= 0 && y < n && grid[x][y] == '1') {
grid[x][y] = '0';
stk.push(new int[] {x, y});
}
}
}
++ans;
}
}
}
return ans;
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31 | class Solution {
public:
int numIslands(vector<vector<char>>& grid) {
int m = grid.size();
int n = grid[0].size();
int ans = 0;
int dirs[5] = {-1, 0, 1, 0, -1};
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if (grid[i][j] != '1') {
continue;
}
vector<pair<int, int>> stk{{i, j}};
grid[i][j] = '0';
while (!stk.empty()) {
auto [a, b] = stk.back();
stk.pop_back();
for (int k = 0; k < 4; ++k) {
int x = a + dirs[k], y = b + dirs[k + 1];
if (x >= 0 && x < m && y >= 0 && y < n && grid[x][y] == '1') {
grid[x][y] = '0';
stk.emplace_back(x, y);
}
}
}
++ans;
}
}
return ans;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27 | func numIslands(grid [][]byte) int {
m, n := len(grid), len(grid[0])
dirs := []int{-1, 0, 1, 0, -1}
ans := 0
for i := 0; i < m; i++ {
for j := 0; j < n; j++ {
if grid[i][j] != '1' {
continue
}
grid[i][j] = '0'
stk := [][2]int{{i, j}}
for len(stk) > 0 {
cur := stk[len(stk)-1]
stk = stk[:len(stk)-1]
for k := 0; k < 4; k++ {
x, y := cur[0]+dirs[k], cur[1]+dirs[k+1]
if x >= 0 && x < m && y >= 0 && y < n && grid[x][y] == '1' {
grid[x][y] = '0'
stk = append(stk, [2]int{x, y})
}
}
}
ans++
}
}
return ans
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28 | function numIslands(grid: string[][]): number {
const m = grid.length;
const n = grid[0].length;
let ans = 0;
const dirs = [-1, 0, 1, 0, -1];
for (let i = 0; i < m; ++i) {
for (let j = 0; j < n; ++j) {
if (grid[i][j] !== '1') {
continue;
}
grid[i][j] = '0';
const stk: number[][] = [[i, j]];
while (stk.length) {
const [a, b] = stk.pop()!;
for (let k = 0; k < 4; ++k) {
const x = a + dirs[k];
const y = b + dirs[k + 1];
if (x >= 0 && x < m && y >= 0 && y < n && grid[x][y] === '1') {
grid[x][y] = '0';
stk.push([x, y]);
}
}
}
ans++;
}
}
return ans;
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34 | const DIRS: [i32; 5] = [-1, 0, 1, 0, -1];
impl Solution {
pub fn num_islands(grid: Vec<Vec<char>>) -> i32 {
let mut grid = grid;
let m = grid.len();
let n = grid[0].len();
let mut ans = 0;
for i in 0..m {
for j in 0..n {
if grid[i][j] != '1' {
continue;
}
grid[i][j] = '0';
let mut stk = vec![(i, j)];
while let Some((a, b)) = stk.pop() {
for k in 0..4 {
let x = a as i32 + DIRS[k];
let y = b as i32 + DIRS[k + 1];
if x >= 0 && y >= 0 {
let (x, y) = (x as usize, y as usize);
if x < m && y < n && grid[x][y] == '1' {
grid[x][y] = '0';
stk.push((x, y));
}
}
}
}
ans += 1;
}
}
ans
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33 | public class Solution {
public int NumIslands(char[][] grid) {
int m = grid.Length;
int n = grid[0].Length;
int ans = 0;
int[] dirs = { -1, 0, 1, 0, -1 };
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if (grid[i][j] != '1') {
continue;
}
grid[i][j] = '0';
var stk = new Stack<(int, int)>();
stk.Push((i, j));
while (stk.Count > 0) {
var (a, b) = stk.Pop();
for (int k = 0; k < 4; ++k) {
int x = a + dirs[k];
int y = b + dirs[k + 1];
if (x >= 0 && x < m && y >= 0 && y < n && grid[x][y] == '1') {
grid[x][y] = '0';
stk.Push((x, y));
}
}
}
ans++;
}
}
return ans;
}
}
|