欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

岛屿数量(BFS广度优先搜索:队列)

程序员文章站 2022-06-12 15:24:19
...

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

示例 1:

输入:
11110
11010
11000
00000

输出: 1
示例 2:

输入:
11000
11000
00100
00011

输出: 3

解题思路:
遍历每一个点,在每一次循环中,判断是否当前点是‘1’;
如果是的话开始BFS,将本点入队,接下来while(队列非空)来将这个点上下左右4个点push到队列中并把它们置为‘0’(如果这4个点是‘1’ && 没有越界的话),不要忘记在这个while中pop掉队头元素
这样在while中能够完成一次岛屿的搜索,出while继续在for(for)中搜索其他岛屿;

伪代码(相当不全面,是思考时候的草纸。。。)

岛屿数量(BFS广度优先搜索:队列)

代码

class Solution {
public:
    int numIslands(vector<vector<char>>& grid) {
        if(grid.empty())
            return 0;
        int row = grid.size(), column = grid[0].size(),count = 0, A = 0, B = 0;
        queue<pair<int, int> > neighbors;
        for(int i = 0;i < row; i++)
        {
            for(int j = 0;j < column; j++)
            {
                if(grid[i][j] == '1')
                {
                    neighbors.push({i,j});
                    grid[i][j] = '0';
                    count++;
                    while(!neighbors.empty())
                    {
                        pair<int,int> temp = neighbors.front();
                        A = temp.first; B = temp.second;
                        neighbors.pop();
                        if(A - 1 >= 0 && grid[A - 1][B] == '1'){
                            neighbors.push({A-1, B});
                            grid[A - 1][B] = '0';
                        }
                        if(A + 1 < row && grid[A + 1][B] == '1'){
                            neighbors.push({A+1, B});
                            grid[A + 1][B] = '0';
                        }
                        if(B - 1 >= 0 && grid[A][B - 1] == '1'){
                            neighbors.push({A, B - 1});
                            grid[A][B - 1] = '0';
                        }
                        if(B + 1 < column && grid[A][B + 1] == '1'){
                            neighbors.push({A, B + 1});
                            grid[A][B + 1] = '0';
                        }
                    }
                }
            }
        }
        return count;
    }
};
相关标签: algorithm practice