tags = ["leetcode","队列","BFS","C++","Go"]
岛屿的个数
给定一个由 '1'（陆地）和 '0'（水）组成的的二维网格，计算岛屿的数量。一个岛被水包围，并且它是通过水平方向或垂直方向上相邻的陆地连接而成的。你可以假设网格的四个边均被水包围。
示例1：输入:11110110101100000000输出: 1
示例2：
输入:11000110000010000011输出: 3
分析
这道题的解法有很多，但本帖用广度优先搜索BFS来解答。
上下左右是否被水（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 que; int count=0; int x=0; int y=0; int xx=0; int yy=0;public: int numIslands(vector >& 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||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 itemtype Item interface {}//ItemQueue is store itemstype ItemQueue struct { items []Item}//ItemQueuer is a interfacetype ItemQueuer interface { New() ItemQueue Push(t Item) Pop() *Item Empty() bool Size() int}//Push a new itemfunc (s *ItemQueue) Push(t Item) { s.items = append(s.items, t)}//Pop a front itemfunc (s *ItemQueue) Pop() { s.items = s.items[1:]}//Empty of itemsfunc (s *ItemQueue) Empty() bool { return len(s.items) == 0}//Size of itemsfunc (s *ItemQueue) Size() int { return len(s.items)}//Front of itemsfunc (s *ItemQueue) Front() Item { return s.items[0]}//Back of itemsfunc (s *ItemQueue) Back() Item { return s.items[len(s.items)-1]} 我们用接口实现了类似C++泛型的queue类，下面是go语言实现：
package mainimport ( "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) que.Pop() for 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}