Medium · Matrices

Battleships in a Board

Given an m × n board whose cells are 'X' (ship) or '.' (water), where every battleship is a straight 1 × k or k × 1 line of X cells and no two ships touch horizontally or vertically, return the number of battleships.

Examples

Example 1

{
  "board": [
    ["X", ".", ".", "X"],
    [".", ".", ".", "X"],
    [".", ".", ".", "X"]
  ]
}

Output: 2 battleships

Example 2

{
  "board": [
    ["X", ".", "X", "X"],
    ["X", ".", ".", "."],
    ["X", ".", "X", "."]
  ]
}

Output: 3 battleships

Rebuild it in the studio

Read every interview problem free. Ten rooms need no account. A token opens a problem in full — Pro never counts.