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 -~----------~----~----~----~------~----~------~--~---
