Tout d'abord, notez que si et sont tous deux impairs, alors la réponse est "NON". Puisque nous devons partitionner la grille en deux marches enfermées, et que le nombre total de cellules est impair, alors l'une des marches doit passer par un nombre impair de cellules. Si nous colorions toutes les cellules en noir et blanc dans un motif de damier, toute marche enfermée devrait commencer et se terminer à la même couleur. Puisqu'après chaque étape la couleur de la cellule change, nous devons passer par un nombre pair de cellules pour que la marche soit enfermée. Évidemment, la réponse est également "NON" pour les cas où min(n, m)=1, sauf dans le cas où n=1; m=4 ou n=4; m=1. Le reste des cas est possible à résoudre.
Les deux premières sous-tâches peuvent être résolues à la main et codées en dur dans le programme.
Les autres sous-tâches s'appuieront sur une idée selon laquelle nous pouvons construire une marche enfermée dans un rectangle en utilisant un motif en zigzag, où au moins l'une des longueurs des côtés est paire. Afin de construire une solution, nous allons diviser tout le rectangle en deux plus petits.
Pour la troisième sous-tâche, nous pouvons partitionner le rectangle en une pièce de 2 \times 1, et une pièce de 2 \times m-1.
Pour la quatrième sous-tâche, nous pouvons partitionner le rectangle en deux pièces de 2 \times m.
Pour la cinquième sous-tâche, nous pouvons partitionner le rectangle en deux pièces de \frac{n}{2} \times m.
Pour la sixième sous-tâche, nous ne pouvons plus faire aveuglément une coupure à travers l'un des côtés, car si ou est impair, l'un des rectangles pourrait finir par avoir deux côtés de longueur impair, ce qui est impossible à résoudre. Donc, nous devons découper deux rectangles à travers l'un des côtés pairs. Pour une mise en œuvre plus facile, il est possible de faire pivoter la grille si nécessaire, puis de faire une coupure verticale et de la faire pivoter à nouveau : de cette façon, nous n'avons pas besoin de nous soucier de deux cas séparés de coupures.
Complexité : O(n \cdot m)