m × n grid of lamps panel: panel[i][j] = 1 if the lamp is on and 0 if it is off. Two lamps are neighbors if their cells share a side (horizontally or vertically).
In one operation you may switch off a single lamp that is on. Lamps cannot be switched on.
Return the smallest number of operations after which no lit lamp has a lit neighbor.panel=[[1, 1, 1], [0, 1, 0]] → 1
Switching off the middle lamp of the top row is enough: the remaining three lit lamps then have no lit neighbors.
panel=[[1, 1], [1, 1]] → 2
Every lamp touches two others. One lamp is not enough, but switching off a diagonal pair gives [[0, 1], [1, 0]].
panel=[[1, 0, 1], [0, 1, 0]] → 0
The lit lamps only touch at corners, which does not count as being neighbors.
m, n ≤ 300panel[i][j] is 0 or 1panel=[[1, 1, 1], [0, 1, 0]]
1
Run checks the first 3 tests in your browser. Submit checks all 77 tests on the server, hidden ones included.