Ships on the Grid

Medium

You are given a battleship board: a rectangular grid grid where 'X' is a ship cell and '.' is water. Count the ships on the board. Every ship is a straight strip of cells: either one row and several consecutive columns, or one column and several consecutive rows. Two different ships never share a side (they may touch at a corner). Try to do it in a single pass, with O(1) extra memory and without modifying grid.

Example 1

grid=[['X', 'X', '.', 'X'], ['.', '.', '.', 'X'], ['X', '.', '.', '.']] → 3

A horizontal two-cell ship in the top-left corner, a vertical two-cell ship on the right, and a single-cell ship at the bottom left: 3 in total.

Example 2

grid=[['.', 'X'], ['X', '.']] → 2

The cells touch only at a corner, so they are two separate ships.

Example 3

grid=[['.', '.', '.']] → 0

There are no ships.

Constraints

1 ≤ number of rows, number of columns ≤ 200
grid[i][j] is 'X' or '.'
The layout is valid: every side-connected group of 'X' cells is a straight strip

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Depth-First Search Array Matrix

Similar problems

Word Traced on a Letter Grid Medium Drain the Landlocked Ponds Medium Land Regions on a Map Medium Rain Reaching Both Seas Medium Can the Ball Stop at the Target Medium

Input

grid=[['X', 'X', '.', 'X'], ['.', '.', '.', 'X'], ['X', '.', '.', '.']]

Expected

Run checks the first 3 tests in your browser. Submit checks all 71 tests on the server, hidden ones included.