just try to make first row and first column zero with minimum no of moves. after they have become zero , check in matrix for any remaining on state. it there is on state , then it is impossible else , that you have done it.
On Tue, Jan 4, 2011 at 4:40 PM, Ankur Khurana <[email protected]>wrote: > it's exactly the same question as Buttons on codechef. search this forum , > it have been discussed before > > > On Tue, Jan 4, 2011 at 4:13 PM, bittu <[email protected]> wrote: > >> There is a lock which is an N by N grid of switches. Each switch can >> be in one of two states (on/off). The lock is unlocked if all the >> switches are on. The lock is built in such a way that, if you toggle >> some switch, all the switches in its row and its column toggle too >> >> Give an algorithm which, given N and a configuration of the N^2 >> switches, will tell you whether the lock can be unlocked by a sequence >> of switch toggles >> >> Note 1: Can be done in O(N^2) time and O(1) space. >> Note 2: You just need to tell if a sequence which unlocks the lock >> exists (and not the actual sequence) >> >> -- >> You received this message because you are subscribed to the Google Groups >> "Algorithm Geeks" group. >> To post to this group, send email to [email protected]. >> To unsubscribe from this group, send email to >> [email protected]<algogeeks%[email protected]> >> . >> For more options, visit this group at >> http://groups.google.com/group/algogeeks?hl=en. >> >> > -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
