Problem 297639 · hard · Phase 02 Linear Data Structures

Darkening the Switch Panel

2d-lists · simulation · enumeration

A control panel is a grid of light switches given as a list of equal-length strings panel; '1' is a lit light and '0' a dark one. Pressing the switch at (r, c) flips that light and each of its up to four neighbours directly above, below, left and right (lit becomes dark and dark becomes lit). Neighbours outside the panel are ignored.

Return the fewest presses that leave every light dark, or -1 if no sequence of presses does.

Examples

Input:  panel = ["010", "111", "010"]
Output: 1
Explanation: press the centre.

Input:  panel = ["11", "11"]
Output: 4
Explanation: press all four switches; each light is flipped three times.

Input:  panel = ["10"]
Output: -1
Explanation: each press flips both lights, so they can never both be dark.

Constraints

  • 1 <= len(panel) <= 20, 1 <= len(panel[0]) <= 10
  • Trying every set of switches is far too slow: a 20 x 10 panel has 2**200 of them.

Goals

  • See that pressing a switch twice undoes it, so each switch is pressed once or not at all
  • Notice that the top row's presses force every later press
  • Try every top-row choice and simulate the rest row by row
Starting Python…