Δυνητικές Συναρτήσεις & Παζλ με Πίνακες

Πολλά παζλ περιγράφουν διαδικασίες που εξελίσσονται στον χρόνο. Το «κλειδί» είναι να βρεις μια δυνητική συνάρτηση (potential) που μετρά την πρόοδο προς τον στόχο: αν δεν αυξάνει ποτέ ή μειώνεται κατά τουλάχιστον ε σε κάθε βήμα, μπορείς να συμπεράνεις αν και πότε θα φτάσεις στην τελική κατάσταση.

Πρόβλημα:

Δίνεται ένας πίνακας $m\times n$ πραγματικών αριθμών. Επιτρέπεται οποτεδήποτε να αντιστρέφεις τα πρόσημα όλων των στοιχείων μιας γραμμής ή μιας στήλης. Μπορείς πάντα να πετύχεις ώστε όλα τα αθροίσματα γραμμών και στηλών να γίνουν μη αρνητικά;