设为首页 加入收藏

TOP

LeetCode 队列与BFS--岛屿的数量(一)
2018-12-11 18:09:11 】 浏览:86
Tags:LeetCode 队列 BFS-- 岛屿 数量

tags = ["leetcode","队列","BFS","C++","Go"]

岛屿的个数

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

输入:
11110
11010
11000
00000

输出: 1

示例2:

输入:
11000
11000
00100
00011

输出: 3

分析

这道题的解法有很多,但本帖用广度优先搜索BFS来解答。
本题输入是一个二维数组,判断一个岛屿的要素是判断是否该陆地(1)上下左右是否被水(0)包围,也就是说,岛屿的数量=联通陆地(1)的数量。
BFS算法题解如下,通过找到为岛(1)的初始点,然后对临近的岛屿进行依次访问,利用队列对访问的岛屿进行储存,如下列图示:

  +----->
+-+
+1|1 1 1 0
+-+
| 1 1 0 1 0
|
v 1 1 0 0 0

    0 0 0 0 0

当找到初始(1)的时候,将其坐标入队,依据队列的FIFO特性,从队列中取出坐标,对其坐标的上下左右元素进行访问,如果临近的元素为陆地(1),则将其坐标加入队列中等待访问,如果该元素已经被访问,则跳过,重复这一过程,直到队列为空,说明元素周围再也没有陆地,便可看作岛屿。访问过的(1)认为的变为(0)便于后续对未访问的陆地进行查找,岛屿的数量就等于队列为空的遍历次数。其代码如下:

C++实现


class Solution {
private:
        queue<int> que;
        int count=0;
        int x=0;
        int y=0;
        int xx=0;
        int yy=0;
public:
    int numIslands(vector<vector<char>>& grid) {
        int rows=grid.size();
        int cols=rows>0?grid[0].size():0;
        int dx[]={-1,0,1,0};
        int dy[]={0,1,0,-1};
        if(rows==0||cols==0){
            return 0;
        }
        for(int i=0;i<rows;i++){
            for(int j=0;j<cols;j++){
                //cout<<rows<<cols<<endl;//外部两个for循环为从上到下从左到右寻找未访问的陆地,因为访问过的陆地都已经被置零
                if(grid[i][j]=='1'){
                    que.push(i);
                    que.push(j); 
                    grid[i][j]='0';
                    while(!que.empty()){
                        x=que.front();
                        que.pop();
                        y=que.front();
                        que.pop();
                        for(int k=0;k<4;k++){
                            xx=x+dx[k];
                            yy=y+dy[k];
                            if(xx<0||xx>=rows||yy<0||yy>=cols){
                                continue;
                            }
                            if(grid[xx][yy]=='1'){
                                grid[xx][yy]='0';
                                que.push(xx);
                                que.push(yy);
                            }
                        }
                    }
                    count++;//队列为空的次数=岛屿的数量
                }
            }
        }
        return count;
    }
};

Go实现

由于go语言没有队列queue包,我们自己建一个:


package queue
//Item any type's item
type Item interface {
}
//ItemQueue is store items
type ItemQueue struct {
    items []Item
}
//ItemQueuer is a interface
type ItemQueuer interface {
    New() ItemQueue
    Push(t Item)
    Pop() *Item
    Empty() bool
    Size() int
}
//Push a new item
func (s *ItemQueue) Push(t Item) {
    s.items = append(s.items, t)
}

//Pop a front item
func (s *ItemQueue) Pop() {
    s.items = s.items[1:]
}
//Empty of items
func (s *ItemQueue) Empty() bool {
    return len(s.items) == 0
}
//Size of items
func (s *ItemQueue) Size() int {
    return len(s.items)
}
//Front of items
func (s *ItemQueue) Front() Item {
    return s.items[0]
}
//Back of items
func (s *ItemQueue) Back() Item {
    return s.items[len(s.items)-1]
}

我们用接口实现了类似C++泛型的queue类,下面是go语言实现:


package main
import (
    "fmt"
    "self/queue"
    "time"
)
var que queue.ItemQueue//声明一个队列变量
var m = [][]byte{
    {'1', '1', '0', '1', '0'},
    {'1', '1', '0', '1', '0'},
    {'1', '1', '0', '1', '1'},
    {'0', '0', '1', '1', '0'},
}
func main() {
    start := time.Now()
    coun := numIslands(m)
    fmt.Printf("the num of isl is %v", coun)
    cost := time.Since(start)
    fmt.Printf("Cost %s", cost)
}
func numIslands(grid [][]byte) int {
    var que queue.ItemQueue
    var x, y, xx, yy, count, rows, cols int = 0, 0, 0, 0, 0, 0, 0
    rows = len(grid)
    if rows > 0 {
        cols = len(grid[0])
    } else {
        cols = 0
    }
    var dx, dy = []int{-1, 0, 1, 0}, []int{0, 1, 0, -1}
    if rows == 0 || cols == 0 {
        return 0
    }
    for i := 0; i < rows; i++ {
        for j := 0; j < cols; j++ {
            if grid[i][j] == '1' {
                que.Push(i)
                que.Push(j)
                grid[i][j] = '0'
                for !que.Empty() {
                    x = que.Front().(int)//因为储存的是坐标,所以是int,这里要强制转化,因为que.Front()返回的是interface{}类型
                    que.Pop()
                    y = que.Front().(int)

编程开发网
首页 上一页 1 2 下一页 尾页 1/2/2
】【打印繁体】【投稿】【收藏】 【推荐】【举报】【评论】 【关闭】 【返回顶部
上一篇环形链表得golang实现 下一篇Golang中的三个点

评论

帐  号: 密码: (新用户注册)
验 证 码:
表  情:
内  容:

array(4) { ["type"]=> int(8) ["message"]=> string(24) "Undefined variable: jobs" ["file"]=> string(32) "/mnt/wp/cppentry/do/bencandy.php" ["line"]=> int(214) }