In this post, we have a look at using a queue and breath-first search algorithm to solve a Leetcode challenge. The problem is stated as follows.

Given an `m x n`

2D binary grid `grid`

which represents a map of `'1'`

s (land) and `'0'`

s (water), return *the number of islands*.

An **island** is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.

**Example 1:**

**Input:** grid = [
["1","1","1","1","0"],
["1","1","0","1","0"],
["1","1","0","0","0"],
["0","0","0","0","0"]
]
**Output:** 1

## Queue and BFS

In a FIFO data structure, `the first element added to the queue will be processed first`

.

As shown in the picture above, the queue is a typical FIFO data structure. The insert operation is also called enqueue and the new element is always `added at the end of the queue`

. The delete operation is called dequeue. You are only allowed to `remove the first element`

.

## Solution with bfs

The purpose of the breadth-first search is to write down all the branches when facing a junction and then choose one of them to enter, Then record its shunting situation, and then return to another fork, and repeat the operation.

The pseudo-code looks like this:

` 1 `**procedure** BFS(*G*, *root*) **is**
2 let *Q* be a queue
3 label *root* as explored
4 *Q*.enqueue(*root*)
5 **while** *Q* is not empty **do**
6 *v* := *Q*.dequeue()
7 **if** *v* is the goal **then**
8 **return** *v*
9 **for all** edges from *v* to *w* **in** *G*.adjacentEdges(*v*) **do**
10 **if** *w* is not labeled as explored **then**
11 label *w* as explored
12 *Q*.enqueue(*w*)

Kotlin implementation

```
class Solution {
fun numIslands(grid: Array<CharArray>): Int {
//BFS
//find 1 and expands until there is no more 1 connected horizontally and vertically
//increase by 1
var result = 0
val queue: Queue<Pair<Int, Int>> = LinkedList<Pair<Int, Int>>()
for(r in grid.indices){
for (c in grid[0].indices){
if(grid[r][c] == '1'){
result += 1
queue.add(Pair(r, c))
grid[r][c] = '0' //visited
while(!queue.isEmpty()){
val (x, y) = queue.poll()
if(x > 0 && grid[x-1][y] == '1') //compare the left
{
grid[x-1][y] = '0'
queue.add(Pair(x-1, y))
}
if(x < grid.lastIndex && grid[x+1][y] == '1') //compare the right
{
grid[x+1][y] = '0'
queue.add(Pair(x+1, y))
}
if(y > 0 && grid[x][y - 1] == '1') //compare the top
{
grid[x][y - 1] = '0'
queue.add(Pair(x, y - 1))
}
if(y < grid[0].lastIndex && grid[x][y + 1] == '1') //compare the bottom
{
grid[x][y + 1] = '0'
queue.add(Pair(x, y + 1))
}
}
}
}
}
return result
}
}
```

For more algorithm articles, please go here.