Efficient 2D Array Switch Algorithm for Lights Off in n x m Rooms | C++ Function

[boilhats]

Homework Statement

A house has n x m rooms (n and m natural numbers, n>=2 and m>=2) and is represented as a 2 dimensional Array with n rows(0 to n-1)and m columns(0 to m-1).The room at line i( 0 <= i <= n-1) and column j ( 0 <= j <= m-1 ) is identified by the pair of numbers (i,j).All rooms, with the exception of the ones situated on the first line(i=0) and the first colums (j=0),have a switch. Actuating the switch from the room (i,j) leads to the next result: in each of the rooms (i,j) , (i,j-1) , (i-1,j) , (i-1,j-1) ( the room with the switch, the one above, the one on the left and the one above to the left) if the light was on, it turns off , and if it was off it turns on.
b)Write a function that takes as input a 2D array of 1s and 0s ,dimensions m and n as well as i and j representing a room (i,j) with a switch and outputs the array after turning the switch in the room (i,j).
c)Write a C++ function that takes as input a 2D array of 1s and 0s representing the state of the light in the room m, as well as the dimensions n ( n >=2) and m(m>=2) of the array.The function need to return '1' if there is a set of rooms such that actuating the switch in every room once leads to all lights from all the rooms turning off.Otherwise the function returns 0.You can use the function from B.To be used an algorithm as efficient as possible time-wise ; solutions that use backtracking will receive the most points.I know how to do B the only problem is at c), I don't know how should I write using backtracking , otherwise I can think of other solutions.I'm not asking to write the code for me but just to give me an idea of how I should go about solving using backtracking.

This problem was translated by me from another language if you don't understand something you can ask me.

Homework Equations

The Attempt at a Solution

I know how to do b the only problem is at c), I don't know how should I write using backtracking , otherwise I can think of other solutions.I'm not asking to write the code for me but just to give me an idea of how I should go about solving using backtracking.

This problem was translated by me from another language if you don't understand something you can ask me.

 

[.Scott]

I would note that there is exactly one room that is controlled by one switch only. Given the state of the switch in that room, there are then exactly two rooms that are controlled by only one additional switch each. (and so on)