题解 | #岛屿数量#

思路

1、广度优先搜索
2、pair<int, int> 保存坐标
3、遍历每一个点，如果发现是1，那么count++，并将其置为0，然后把这个pos放在队列中（广度优先），当队列不为空的时候做下面的事情：取坐标、判断上下左右是否为1，若为1则加入到队列中并将其置为0（防止重复计数），直至遍历整个二维矩阵

代码

class Solution {
public:
    /**
     * 判断岛屿数量
     * @param grid char字符型vector<vector<>> 
     * @return int整型
     */
    int solve(vector<vector<char> >& grid) {
        // write code here
        int m = grid.size();
        int n = grid[0].size();

        // 先找到一个1
        int count = 0;

        queue<pair<int , int >> q;
        for(int i = 0;i <m;i++){
            for(int j = 0;j < n; j++ ){
                if(grid[i][j]=='1'){        // 找到了
                    count++;
                    q.push(make_pair(i,j));
                    grid[i][j]='0';
                    while(!q.empty()){
                        auto pos = q.front();
                        q.pop();
                        int i = pos.first;
                        int j = pos.second;
                        if(i>=1 && grid[i-1][j] == '1'){
                            q.push(make_pair(i-1,j));
                            grid[i-1][j]=0;
                        }
                        if(i < m-1 && grid[i+1][j] == '1'){
                            q.push(make_pair(i+1,j));
                            grid[i+1][j]=0;

                        }
                        if(j>=1 && grid[i][j-1] == '1'){
                            q.push(make_pair(i,j-1));
                            grid[i][j-1]=0;

                        }
                        if(j < n-1 && grid[i][j+1] == '1'){
                            q.push(make_pair(i,j+1));
                            grid[i][j+1]=0;

                        }



                    }
                }
            }
        }

        return count;
    }
};