| comments | difficulty | edit_url | tags | |||||
|---|---|---|---|---|---|---|---|---|
true |
Medium |
|
Given an m x n 2D binary grid grid which represents a map of '1's (land) and '0's (water), return the number of islands.
An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.
Example 1:
Input: grid = [ ["1","1","1","1","0"], ["1","1","0","1","0"], ["1","1","0","0","0"], ["0","0","0","0","0"] ] Output: 1
Example 2:
Input: grid = [ ["1","1","0","0","0"], ["1","1","0","0","0"], ["0","0","1","0","0"], ["0","0","0","1","1"] ] Output: 3
Constraints:
m == grid.lengthn == grid[i].length1 <= m, n <= 300grid[i][j]is'0'or'1'.
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 ansclass 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};
function<void(int, int)> dfs = [&](int i, int j) {
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;
}
};using System;
using System.Collections.Generic;
using System.Linq;
public class Solution {
public int NumIslands(char[][] grid)
{
var queue = new Queue<Tuple<int, int>>();
var lenI = grid.Length;
var lenJ = lenI == 0 ? 0 : grid[0].Length;
var paths = new int[,] { { 0, 1 }, { 1, 0 }, { 0, -1 }, { -1, 0 } };
var result = 0;
for (var i = 0; i < lenI; ++i)
{
for (var j = 0; j < lenJ; ++j)
{
if (grid[i][j] == '1')
{
++result;
grid[i][j] = '0';
queue.Enqueue(Tuple.Create(i, j));
while (queue.Any())
{
var position = queue.Dequeue();
for (var k = 0; k < 4; ++k)
{
var next = Tuple.Create(position.Item1 + paths[k, 0], position.Item2 + paths[k, 1]);
if (next.Item1 >= 0 && next.Item1 < lenI && next.Item2 >= 0 && next.Item2 < lenJ && grid[next.Item1][next.Item2] == '1')
{
grid[next.Item1][next.Item2] = '0';
queue.Enqueue(next);
}
}
}
}
}
}
return result;
}
}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 ansclass 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';
}
}
}
}
}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)
)