200

LeetCode medium original: C# #csharp #graph #leetcode #matrix #medium #search #string
El texto de la tarea se traduce del ruso para el idioma seleccionado. El código no cambia.
LeetCode Static

. Number of Islands

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

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

Ejemplo:

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# solución

coincidente/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++ solución

borrador automático, revisar antes de enviar 
#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 solución

borrador automático, revisar antes de enviar 
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;
    }
}

Algorithm

1️⃣

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

2️⃣

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

3️⃣

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

😎

Vacantes para esta tarea

Se muestran vacantes activas con etiquetas coincidentes.

Todas las vacantes
Todavía no hay vacantes activas.