プログラミングトレーニング————島の数(C++)

島の数

タイトル説明

主な思想

深度優先探索

広さ優先探索

コード実装

深度優先探索

広さ優先探索

タイトルの説明
「1」(陸地)と「0」(水)からなる2次元メッシュをあげます.メッシュ内の島の数を計算してください.
島は常に水に囲まれており、各島は水平方向または垂直方向に隣接する陸続きでしか形成できない.
さらに、メッシュの4つのエッジが水で囲まれていると仮定できます.
例1:
入力:[‘1’,‘1’,‘1’,‘1’,‘1’,‘0’],[‘1’,‘0’,‘1’,‘0’,‘1’,‘0’,[‘1’,‘1’,‘1’,‘0’,‘0’,‘0’,‘0’,[‘0’,‘0’,‘0’,‘0’,‘0’,‘0’,‘0’,’]出力:1
例2:
入力:[‘1’,‘1’,‘0’,‘0’,‘0’,‘0’,‘0’],[‘1’,‘0’,‘0’,‘0’,‘0’],[‘0’,‘0’,‘1’,‘0’,‘0’,‘0’,[‘0’,‘0’,‘0’,‘0’,‘1’]]出力:3解釈:各島は水平および/または垂直方向に隣接する陸地でしか接続できない.
ソース:力ボタン(LeetCode)リンク:https://leetcode-cn.com/problems/number-of-islands著作権はインターネットの所有に帰属する.商業転載は公式の授権に連絡してください.非商業転載は出典を明記してください.
主な思想.
深度優先検索
メッシュをスキャンし、数字が「1」の座標を見つけ、深さ優先検索を行い、検索された1ごとに0に変更し、繰り返し検索を防止し、深さ検索を何回したか、何個の島があるかを防止します.
広さ優先検索
メッシュをスキャンし、数字が「1」の座標を見つけてキューに入れ、広さ優先検索を行い、検索された1ごとに0に変更し、キューが空いているときに終了し、広さ検索を何回したかで、どれだけの島があるかを検索します.
コード実装
公式サイトよりhttps://leetcode-cn.com/problems/number-of-islands/solution/dao-yu-shu-liang-by-leetcode/
深度優先検索

class Solution {
     
private:
    void dfs(vector<vector<char>>& grid, int r, int c) {
     
        int nr = grid.size();//       
        int nc = grid[0].size();//      

        grid[r][c] = '0';//    1      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(vector<vector<char>>& grid) {
     
        int nr = grid.size();
        if (!nr) return 0;
        int nc = grid[0].size();

        int num_islands = 0;
        for (int r = 0; r < nr; ++r) {
     
            for (int c = 0; c < nc; ++c) {
     
                if (grid[r][c] == '1') {
     
                    ++num_islands;//       
                    dfs(grid, r, c);
                }
            }
        }

        return num_islands;
    }
};

広さ優先検索

class Solution {
     
public:
    int numIslands(vector<vector<char>>& grid) {
     
        int nr = grid.size();//      
        if (!nr) return 0;
        int nc = grid[0].size();//      

        int num_islands = 0;//      
        //    
        for (int r = 0; r < nr; ++r) {
     
            for (int c = 0; c < nc; ++c) {
     
                if (grid[r][c] == '1') {
     
                    ++num_islands;
                    grid[r][c] = '0';
                    queue<pair<int, int>> neighbors;//    
                    neighbors.push({
     r, c});//   
                    while (!neighbors.empty()) {
     
                        auto rc = neighbors.front();
                        neighbors.pop();
                        int row = rc.first, col = rc.second;//    
                        //                 
                        if (row - 1 >= 0 && grid[row-1][col] == '1') {
     
                        //     ，     ，      0
                            neighbors.push({
     row-1, col});
                            grid[row-1][col] = '0';
                        }
                        if (row + 1 < nr && grid[row+1][col] == '1') {
     
                            neighbors.push({
     row+1, col});
                            grid[row+1][col] = '0';
                        }
                        if (col - 1 >= 0 && grid[row][col-1] == '1') {
     
                            neighbors.push({
     row, col-1});
                            grid[row][col-1] = '0';
                        }
                        if (col + 1 < nc && grid[row][col+1] == '1') {
     
                            neighbors.push({
     row, col+1});
                            grid[row][col+1] = '0';
                        }
                    }
                }
            }
        }

        return num_islands;
    }
};