Steinhaus' problem on the chessboard

An algorithm for solving the following problem is given. The squares of the chessboard or a more general $m\times n$ board are divided between a king and a rook in such a way that each of the pieces can move (according to the usual rules) just over its own squares. The problem is to prove that either the king can find its way from the left edge of the board to the right edge or the rook crosses the board from the bottom row to the top one.