419. Battleships in a Board - Detailed Explanation

Problem Statement

You’re given an m×n board represented by a 2D character array board, where:

• 'X' represents part of a battleship
• '.' represents empty water

Battleships are placed either horizontally or vertically (no diagonal), and no two battleships touch each other (not even corner‑to‑corner). Count how many distinct battleships are on the board.

Examples

Example 1

Input:
board = [
  ["X",".",".","X"],
  [".",".",".","X"],
  [".",".",".","X"]
]
Output: 2
Explanation:
There’s one vertical ship of length 1 at (0,0),
and one vertical ship of length 3 at the rightmost column.

Example 2

Input:
board = [
  ["X","X","X"]
]
Output: 1
Explanation:
One horizontal ship of length 3.

Example 3

Input:
board = [
  [".",".","."],
  [".",".","."]
]
Output: 0
Explanation:
No battleships.

Constraints

• 1 ≤ m, n ≤ 200
• board[i][j] is 'X' or '.'
• Ships only occupy contiguous 'X' cells in a row or column, and are separated by at least one '.'.

Hints

1. How would you “erase” a ship once you find one to avoid counting it again?
2. Can you count ships by examining only a single cell per ship—say the “head” of each?

Brute Force (Flood‑Fill) Approach

Idea

Whenever you encounter an unvisited 'X', that’s a new ship. Use DFS (or BFS) to mark all connected 'X' cells of that ship as visited so you don’t recount it.

Steps

1. Initialize count = 0.
2. For each cell (i,j):
   • If board[i][j] == 'X', increment count, then flood‑fill from (i,j)—changing all reachable 'X' (up/down/left/right) to '.'.
3. Return count.

Optimal (One‑Pass) Approach

Idea

Each battleship has exactly one “head” cell—the top‑leftmost cell of that ship. It’s the only 'X' with no 'X' immediately above or to the left. Count those.

Steps

1. Initialize count = 0.
2. For each cell (i,j):
   • If board[i][j] == 'X'
     and (i==0 or board[i-1][j]=='.')
     and (j==0 or board[i][j-1]=='.')
     then count++.
3. Return count.

Python Code