| 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 {
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);
}
}
}
}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};
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;
}
};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
}function numIslands(grid: string[][]): number {
const m = grid.length;
const n = grid[0].length;
let ans = 0;
const dfs = (i: number, j: number) => {
if (grid[i]?.[j] !== '1') {
return;
}
grid[i][j] = '0';
dfs(i + 1, j);
dfs(i - 1, j);
dfs(i, j + 1);
dfs(i, j - 1);
};
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;
}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
}
}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 {
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)> bfs = [&](int i, int j) {
grid[i][j] = '0';
queue<pair<int, int>> q;
q.push({i, j});
vector<int> dirs = {-1, 0, 1, 0, -1};
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;
}
};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
}function numIslands(grid: string[][]): number {
const m = grid.length;
const n = grid[0].length;
let ans = 0;
function bfs(i, j) {
grid[i][j] = '0';
let q = [[i, j]];
const dirs = [-1, 0, 1, 0, -1];
while (q.length) {
[i, j] = q.shift();
for (let k = 0; k < 4; ++k) {
const x = i + dirs[k];
const y = j + dirs[k + 1];
if (x >= 0 && x < m && y >= 0 && y < n && 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;
}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
}
}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)
)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];
}
}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;
}
};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
}function numIslands(grid: string[][]): number {
const m = grid.length;
const n = grid[0].length;
let p = [];
for (let i = 0; i < m * n; ++i) {
p.push(i);
}
function find(x) {
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 (x < m && y < n && 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;
}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
}
}