200. Number of Islands

LeetCode medium original: C# #csharp #graph #leetcode #matrix #medium #search #string
Le texte du problème est traduit du russe pour la langue sélectionnée. Le code reste inchangé.
LeetCode Static

Дана двумерная бинарная сетка размером m x n, представляющая карту из '1' (земля) и '0' (вода). return количество островов.

Остров окружён водой и образуется путём соединения соседних земель горизонтально или вертикально. Можно предположить, что все четыре края сетки окружены водой.

Exemple:

Input: grid = [

["1","1","1","1","0"],

["1","1","0","1","0"],

["1","1","0","0","0"],

["0","0","0","0","0"]

]

Output: 1

C# solution

correspondant/original 
public class Solution {
    private void Dfs(char[][] grid, int r, int c) {
        int nr = grid.Length;
        int nc = grid[0].Length;
        grid[r][c] = '0';
        if (r - 1 >= 0 && grid[r - 1][c] == '1') Dfs(grid, r - 1, c);
        if (r + 1 < nr && grid[r + 1][c] == '1') Dfs(grid, r + 1, c);
        if (c - 1 >= 0 && grid[r][c - 1] == '1') Dfs(grid, r, c - 1);
        if (c + 1 < nc && grid[r][c + 1] == '1') Dfs(grid, r, c + 1);
    }
    public int NumIslands(char[][] grid) {
        int nr = grid.Length;
        if (nr == 0) return 0;
        int nc = grid[0].Length;
        int numIslands = 0;
        for (int r = 0; r < nr; ++r) {
            for (int c = 0; c < nc; ++c) {
                if (grid[r][c] == '1') {
                    numIslands++;
                    Dfs(grid, r, c);
                }
            }
        }
        return numIslands;
    }
}

C++ solution

brouillon automatique, à relire avant soumission 
#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    private void Dfs(char[][] grid, int r, int c) {
        int nr = grid.size();
        int nc = grid[0].size();
        grid[r][c] = '0';
        if (r - 1 >= 0 && grid[r - 1][c] == '1') Dfs(grid, r - 1, c);
        if (r + 1 < nr && grid[r + 1][c] == '1') Dfs(grid, r + 1, c);
        if (c - 1 >= 0 && grid[r][c - 1] == '1') Dfs(grid, r, c - 1);
        if (c + 1 < nc && grid[r][c + 1] == '1') Dfs(grid, r, c + 1);
    }
    public int NumIslands(char[][] grid) {
        int nr = grid.size();
        if (nr == 0) return 0;
        int nc = grid[0].size();
        int numIslands = 0;
        for (int r = 0; r < nr; ++r) {
            for (int c = 0; c < nc; ++c) {
                if (grid[r][c] == '1') {
                    numIslands++;
                    Dfs(grid, r, c);
                }
            }
        }
        return numIslands;
    }
}

Java solution

brouillon automatique, à relire avant soumission 
import java.util.*;
import java.math.*;

// Auto-generated Java draft from the C# solution. Review API differences before LeetCode submit.
public class Solution {
    private void Dfs(char[][] grid, int r, int c) {
        int nr = grid.length;
        int nc = grid[0].length;
        grid[r][c] = '0';
        if (r - 1 >= 0 && grid[r - 1][c] == '1') Dfs(grid, r - 1, c);
        if (r + 1 < nr && grid[r + 1][c] == '1') Dfs(grid, r + 1, c);
        if (c - 1 >= 0 && grid[r][c - 1] == '1') Dfs(grid, r, c - 1);
        if (c + 1 < nc && grid[r][c + 1] == '1') Dfs(grid, r, c + 1);
    }
    public int NumIslands(char[][] grid) {
        int nr = grid.length;
        if (nr == 0) return 0;
        int nc = grid[0].length;
        int numIslands = 0;
        for (int r = 0; r < nr; ++r) {
            for (int c = 0; c < nc; ++c) {
                if (grid[r][c] == '1') {
                    numIslands++;
                    Dfs(grid, r, c);
                }
            }
        }
        return numIslands;
    }
}

Python solution

correspondant/original 
class Solution:
    def numIslands(self, grid):
        if not grid:
            return 0

        num_islands = 0
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if grid[i][j] == "1":
                    self.dfs(grid, i, j)
                    num_islands += 1

        return num_islands

    def dfs(self, grid, r, c):
        if (
            r < 0
            or c < 0
            or r >= len(grid)
            or c >= len(grid[0])
            or grid[r][c] != "1"
        ):
            return
        grid[r][c] = "0"

        self.dfs(grid, r - 1, c)
        self.dfs(grid, r + 1, c)
        self.dfs(grid, r, c - 1)
        self.dfs(grid, r, c + 1)

Go solution

correspondant/original 
package main

func numIslands(grid [][]byte) int {
    if len(grid) == 0 {
        return 0
    }

    numIslands := 0
    for i := 0; i < len(grid); i++ {
        for j := 0; j < len(grid[0]); j++ {
            if grid[i][j] == '1' {
                dfs(grid, i, j)
                numIslands++
            }
        }
    }
    return numIslands
}

func dfs(grid [][]byte, r, c int) {
    if r < 0 || c < 0 || r >= len(grid) || c >= len(grid[0]) || grid[r][c] != '1' {
        return
    }

    grid[r][c] = '0'
    dfs(grid, r-1, c)
    dfs(grid, r+1, c)
    dfs(grid, r, c-1)
    dfs(grid, r, c+1)
}

Algorithm

Линейно просканируйте двумерную карту, если узел содержит '1', то это корневой узел, который запускает Depth-first search (DFS).

Во время выполнения DFS каждый посещённый узел следует установить в '0', чтобы пометить его как посещённый.

Подсчитайте количество корневых узлов, запускающих DFS. Это количество будет равно количеству островов, так как каждый DFS, начинающийся с какого-либо корня, идентифицирует остров.

😎

Vacancies for this task

offres actives with overlapping task tags are affichés.

Toutes les offres
Il n'y a pas encore d'offres actives.