Fewest Cross Strikes

Medium

You get a small grid board of 0s and 1s. A move is a **cross strike**: pick a cell that currently holds 1 and set its entire row and entire column to 0. Return the smallest number of strikes after which the grid has no 1s left.

Example 1

board=[[1, 1, 0], [0, 1, 1]] → 2

Striking (0, 1) clears row 0 and column 1; the 1 at (1, 2) remains and takes a second strike. No single strike covers every 1.

Example 2

board=[[0, 1], [1, 1]] → 1

Striking (1, 1) clears row 1 and column 1, which is enough.

Example 3

board=[[0, 0, 0]] → 0

There are no 1s, so no strikes are needed.

Constraints

1 ≤ len(board), len(board[0]) ≤ 6
All rows have the same length
board[i][j] is 0 or 1

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Bit Manipulation Breadth-First Search Array Matrix

Similar problems

Keys and Doors in a Maze Hard Turn Every Lamp Off Hard Drain the Landlocked Ponds Medium Land Regions on a Map Medium Steps to the Nearest Exit Medium

Input

board=[[1, 1, 0], [0, 1, 1]]

Expected

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