200. Number of Islands

LeetCode medium original: C# #csharp #graph #leetcode #matrix #medium #search #string

선택한 UI 언어에 맞게 문제 텍스트를 러시아어에서 번역합니다. 코드는 변경하지 않습니다.

LeetCode Static

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

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

예제:

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# 해법

매칭됨/원본

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++ 해법

자동 초안, 제출 전 검토

#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 해법

자동 초안, 제출 전 검토

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 해법

매칭됨/원본

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 해법

매칭됨/원본

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

활성 채용 with overlapping task tags are 표시됨.

전체 채용

아직 활성 채용이 없습니다.