Hello!

I would highly appreciate any hint on the following problem. I assume there must exist a solution that doesn’t involve linear algebra (or backtracking).

**Problem statement:**

A house consists of n × m rooms (n, m ∈ N, n, m ≥ 2) and is represented by a matrix with n lines and m columns. All rooms, except those on the first line (i = 0) and those on the first column (j = 0) have a switch.

Switching a light in one of the rooms produces the following effect: the room with the switch (i,j), the room above the switch (i-1, j), the room on the left of switch (i,j-1) and the room on the upper-left diagonal of the switch (i-1, j-1) will have their lights turned off if they were on and will have their lights turned on if they were off.

Write a function that receives a matrix of 0s and 1s and returns 1 if there is a subset of rooms such that switching the lights in every room of this subset, results in all the rooms in the house having their lights turned off. Otherwise return 0.

**Example**

For the following matrix, 1 represents a room with a light that is turned on and 0 represents a room with a light that is turned off:

0 1 1 0

0 1 0 1

0 0 1 1

0 0 0 0

0 0 0 0

By switching the lights in rooms: { {1,2}, {2,3} } all lights in the house are turned off. So there is at least one solution.

Thanks a lot! Again, any hint is appreciated.