прямоугольная комната

Прямоугольную комнату размерами M на N (сначала по горизонтали, а потом по вертикали) замостили треугольными плитками и их пронумеровали, как показано на рисункеЗа один шаг можно переместиться с одной паркетины на другую только через общую сторону