It seems it is possible to have unreachable destnation matrix. However I have last query. Is it possible to use initial and final matrix to determine if one is reachable from other through toggle operations without actually performing them?
_dufus On Sep 19, 8:21 pm, Dufus <rahul.dev.si...@gmail.com> wrote: > 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 <maleki...@gmail.com> 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 <bharath1...@gmail.com> 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 algogeeks@googlegroups.com To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/algogeeks -~----------~----~----~----~------~----~------~--~---
