Turn Every Lamp Off

Hard

A panel is an m × n grid of lamps lamps: 1 means the lamp is on, 0 means it is off. Pressing a lamp toggles it and its side neighbours (above, below, left and right, where they exist): lamps that were on go off, and lamps that were off come on. Return the fewest presses after which every lamp is off, or -1 if that is impossible.

Example 1

lamps=[[1, 1, 0], [1, 0, 0]] → 1

A single press on lamp (0, 0) toggles it and its neighbours (0, 1) and (1, 0), and all three go dark.

Example 2

lamps=[[1, 0], [0, 0]] → 3

To turn off one corner lamp of a 2 × 2 panel, press it and both of its neighbours: 3 presses.

Example 3

lamps=[[0, 1, 0]] → 3

Constraints

1 ≤ m, n ≤ 4
all rows of the grid have the same length
lamps[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 Hash Table Matrix

Similar problems

Keys and Doors in a Maze Hard Smallest Balanced Set of Rows Hard A Board Cut by Slashes Medium Fewest Cross Strikes Medium Total of the Unreachable Medium

Input

lamps=[[1, 1, 0], [1, 0, 0]]

Expected

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