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.