# Island Count

Given a 2d grid map of `'1'`s (land) and `'0'`s (water), count the number of islands. Two land spaces are connected if they are adjacent horizontally or vertically, but not diagonally.

Example:

`.0....00......0`

`..000...000...000..0......000.`

Now how would we write a program that takes as input an island map and returns the number of islands?

We notice that at a base level, we will have to examine a position on the grid, evaluate it, and move on to our next. These sorts of problems generally lend themselves to a recursive solution and the algorithm will follow along these lines:

`1. Examine the current state, if the current state is a solution:2. Handle the solution3. Else, examine all the next decisions and implement them4. Check if it’s valid and if so,5. Recursively check if it’s a solution6. Make the decision and move on to the next one`

When coded, we would end up with something like this

`function countIslands(islandMap) {`
`var destroyIsland = function(island, i, j) {    // 3. Else, consider all next decisions and implement them    if (islandArray[i] &&         i < islandArray.length &&         j < islandArray[i].length &&         islandArray[i][j] === '0') { `
`      // 4. Check if it’s valid and if so,      islandArray[i][j] = 'destroyed';`
`// 5. Recursively check if it’s a solution      // 6. Make the decision and move on to the next one      destroyIsland(islandArray, i+1, j)      destroyIsland(islandArray, i, j+1)      destroyIsland(islandArray, i-1, j)      destroyIsland(islandArray, i, j-1)    }  }`
`for (var i = 0; i < islandArray.length; i++) {    for (var j = 0; j < islandArray[i].length; j++) {      // 1. Examine the current state, if the current state is a solution:      if (islandArray[i][j] === '0') {        // 2. Handle the solution         count++        destroyIsland(islandArray, i, j)}`

Let’s examine this one by one.

First, we iterate through every element in the 2d array and examine that element. If that element is indeed an island, we increase the count by 1. Then, we examine all the next decisions with `destroyIsland` .

`for (var i = 0; i < islandArray.length; i++) {    for (var j = 0; j < islandArray[i].length; j++) {      if (islandArray[i][j] === '0') {        count++        destroyIsland(islandArray, i, j)}`

In destroyIsland, we check whether the decision was valid (whether it was an island via `===’0'`), and if so we destroy it. Otherwise, we examine all the next decisions and recursively check if each is a solution.

`var destroyIsland = function(island, i, j) {    if (islandArray[i] &&         i < islandArray.length &&         j < islandArray[i].length &&         islandArray[i][j] === '0') {`
`      islandArray[i][j] = 'destroyed';      destroyIsland(islandArray, i+1, j)      destroyIsland(islandArray, i, j+1)      destroyIsland(islandArray, i-1, j)      destroyIsland(islandArray, i, j-1)    }  }`