Steinhaus' problem on the chessboard

Предложен алгоритм решения следующей задачи Штейнгауза. Пусть все поля шахматной доски размера $m\times n$ поделены произвольным образом между королем и ладьей так, что каждая из этих фигур может ходить (в соответствии с обычными шахматными правилами) только по своим полям. Доказать, что либо король может пройти от левого края доски к правому, либо ладья – от нижнего края к верхнему.