Find the total number of distinct landmasses. In a 2D grid where each cell is either land (represented by '1') or water (represented by '0'). Two land cells are considered part of the same landmass if they are adjacent horizontally or vertically.

Hint

Start an initial count of islands to 0. Create a "visited" matrix to keep track of which parts of the original matrix have already been explored. Initially, all positions in the "visited" matrix are marked as empty, "not visited."

Examine each position in the original matrix, if the current position has a value of 1 (representing land) and has not been visited before, increase the island count by 1. and mark the current position as "visited." Perform a "depth-first search" to explore all eight neighboring positions (up, down, left, right, and diagonals) that are also land and have not been visited yet. The depth-first search recursively explores connected land areas. If a neighboring position is land and not visited, mark the neighboring position as "visited." Continue the depth-first search from the neighboring position.

After examining all positions in the original matrix, the algorithm returns the final count of islands found.

# Python implementation

matrix = [
  [1, 0, 0, 0, 1],
  [0, 1, 0, 1, 0],
  [1, 0, 0, 0, 1],
  [1, 0, 1, 0, 0],
  [0, 0, 0, 1, 0]
]

h = len(matrix)
w = len(matrix[0])
visited = [["" for x in y] for y in matrix]

count = 0

def markVisited(y, x):
  visited[y][x] = True

  ROWS = [-1, -1, -1, 0, 0, 1, 1, 1]
  COLS = [-1, 0, 1, -1, 1, -1, 0, 1]

  for i in range(len(ROWS)):
    I = y + ROWS[i]
    J = x + COLS[i]

    if I >= 0 and I < h and J >= 0 and J < w and matrix[I][J] == 1 and not visited[I][J]:
      markVisited(I, J)

for i in range(h):
  for j in range(w):
    if matrix[i][j] == 1 and not visited[i][j]:
      count += 1
      markVisited(i, j)

print(count)

// Javascript implementation

const matrix = [
  [1, 0, 0, 0, 1],
  [0, 1, 0, 1, 0],
  [1, 0, 0, 0, 1],
  [1, 0, 1, 0, 0],
  [0, 0, 0, 1, 0]
];

const h = matrix.length;
const w = matrix[0].length;
const visited = matrix.map(item => item.map(i => ""));

let count = 0;

function markVisited(y, x) {
  visited[y][x] = true;

  let ROWS = [-1, -1, -1, 0, 0, 1, 1, 1];
  let COLS = [-1, 0, 1, -1, 1, -1, 0, 1];

  for (let i = 0; i < ROWS.length; i++) {
    let I = y + ROWS[i]
    let J = x + COLS[i]

    if (I >= 0 && I < h && J >= 0 && J < w && matrix[I][J] == 1 && !visited[I][J]) {
      markVisited(I, J);
    }
  }
}

for (let i = 0; i < h; i++) {
  for (let j = 0; j < w; j++) {
    if (matrix[i][j] == 1 && !visited[i][j]) {
      count++;
      markVisited(i, j)
    }
  }
}

console.log(count);

Find number of islands inside a matrix.

Hint