Minimize Manhattan distance travel algorithm
You could always try the A* algorithm.  It might not be optimal but it is something you could try, and depending on how big the matrix is it might be good enough.  You'll need to design an appropriate heuristic (e.g., maybe the number of elements that are non-zero, divided by two?).