岛屿的个数 — Leetcode 217

岛屿的个数 — Leetcode 217

题目:

给定一个由 '1'(陆地)和 '0'(水)组成的的二维网格,计算岛屿的数量。一个岛被水包围,并且它是通过水平方向或垂直方向上相邻的陆地连接而成的。你可以假设网格的四个边均被水包围。

示例 1:

输入:
11110
11010
11000
00000

输出: 1

示例 2:

输入:
11000
11000
00100
00011

输出: 3

思路:
使用BFS解法:从头开始检索到第一个1,开始压栈处理操作,向上下左右分别压入其子节点,再将处理过的结点标记为0,当栈内没有元素时,再从头开始寻找1,则此时就是另一个岛屿了(ans++)。

代码:
class Solution {
public:
    int numIslands(vector<vector<char>>&amp; grid) {
        int ans = 0;
        int length = grid.size();
        if(length == 0) return 0;
        int width = grid[0].size();

        queue<pair<int,int>> myQ; 
        for(int i = 0;i<length;i++)
        {
            for(int j = 0;j<width;j++)
            {
                if(grid[i][j] == '1')
                {
                    grid[i][j] = '0';
                    myQ.push(make_pair(i,j));
                    while(1){
                        int size = myQ.size();
                        if(myQ.empty()) {ans++;break;}
                        for(int n = 0;n<size;n++)
                        {
                            auto front = myQ.front();
                            if(front.first+1<length&amp;&amp;grid[front.first+1][front.second]=='1')
                            {
                                myQ.push(make_pair(front.first+1,front.second));
                                grid[front.first+1][front.second]='0';
                            }
                            if(front.second+1<width&amp;&amp;grid[front.first][front.second+1]=='1')
                            {
                                myQ.push(make_pair(front.first,front.second+1));
                                grid[front.first][front.second+1]='0';
                            }   
                            if(front.second-1>=0&amp;&amp;grid[front.first][front.second-1]=='1')
                            {
                                myQ.push(make_pair(front.first,front.second-1));
                                grid[front.first][front.second-1]='0';
                            }
                            if(front.first-1>=0&amp;&amp;grid[front.first-1][front.second]=='1')
                            {
                                myQ.push(make_pair(front.first-1,front.second));
                                grid[front.first-1][front.second]='0';
                            }
                            myQ.pop();
                        }
                    }
                }
            }
        }      
        return ans;
    }
};
5+
Rhett Peng

软件工程大三在读学生,用个人网站记录学习动态