Does it means that every M*N matrix is reachable from a given M*N matrix. In other words is it possible that there is no sequence of toggle operation using which the final matrix can be reached?
_dufus On Sep 19, 5:54 pm, MrM <[email protected]> wrote: > its a beautiful classical problem :) > first its easier to find which blocks needs to be toggled ! (it can be > done by xor) > so your initial matrix changes to : > 1 1 0 > 0 0 1 > 0 0 1 > now we want to set all blocks to 0. its obvious that if we toggle a > row or column twice, the result is as same as do nothing ! > so we can conclude that each block can be toggled at most twice (once > by its row and once by its column). > the point in this problem is that there cannot be more than 2 way to > change the initial matrix to final matrix ! > because if you toggle the first row, you can find that which columns > should be toggled (by their common block with first row), and then you > can denote the status of remaining rows ! > so once you toggle first row and once not ! > another point is that both this ways, are the same ! it means if you > reached the final state by toggling X rows and columns, you will reach > the final state by toggling the remaining 2*N-X rows and columns too ! > if you couldn't reach the final state with this way, you can be sure > that its impossible to reach the final state ! > and if you made it, the minimal number if moves is equal to MIN (X, > 2*N - X) > you can also use this method for an M*N matrix ! > > Hope it helps ^-^ > > On Sep 19, 3:02 pm, Bharath Kumar <[email protected]> wrote: > > > Given two square matrices(initial and final) consisting of elements either > > 1 or 0. Using minimum number of toggles change the initial to final matrix. > > > You can toggle either a single row or column at a time. If ith row is > > toggled all 1's become 0 and vice versa in that row. > > > What will be the correct algorithm for this? > > > For example |0 0 1| |1 1 1| |1 0 1| to |1 1 1| |1 1 0| |1 0 0| would require > > 1st row and last column toggle. --~--~---------~--~----~------------~-------~--~----~ 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 -~----------~----~----~----~------~----~------~--~---
