Po pierwsze, zauważ, że jeśli zarówno , jak i są nieparzyste, to odpowiedź brzmi "NIE". Ponieważ musimy podzielić siatkę na dwa zamknięte spacery, a całkowita liczba komórek jest nieparzysta, to jeden z spacerów musi przechodzić przez nieparzystą liczbę komórek. Jeśli pokolorujemy wszystkie komórki na czarno i biało w wzór szachownicy, każdy zamknięty spacer musiałby zaczynać i kończyć na tym samym kolorze. Ponieważ po każdym kroku kolor komórki się zmienia, musimy przejść przez parzystą liczbę komórek, aby spacer był zamknięty. Oczywiście odpowiedź brzmi również "NIE" w przypadkach, gdy min(n, m)=1, z wyjątkiem przypadku, gdy n=1; m=4 lub n=4; m=1. Pozostałe przypadki można rozwiązać.
Pierwsze dwa podzadania można rozwiązać ręcznie i wprowadzić na stałe do programu.
Pozostałe podzadania będą opierać się na pomyśle, że możemy skonstruować zamknięty spacer w prostokącie, używając wzoru zygzakowatego, gdzie co najmniej jedna z długości boków jest parzysta. Aby skonstruować rozwiązanie, podzielimy cały prostokąt na dwa mniejsze.
Dla trzeciego podzadania możemy podzielić prostokąt na kawałek 2 \times 1 i kawałek 2 \times m-1.
Dla czwartego podzadania możemy podzielić prostokąt na dwa kawałki 2 \times m.
Dla piątego podzadania możemy podzielić prostokąt na dwa kawałki \frac{n}{2} \times m.
Dla szóstego podzadania nie możemy już bezmyślnie przeciąć jednego z boków, ponieważ jeśli lub jest nieparzyste, jeden z prostokątów może mieć dwie boki o nieparzystej długości, co jest niemożliwe do rozwiązania. Musimy więc wyciąć dwa prostokąty wzdłuż jednego z parzystych boków. Dla łatwiejszej implementacji można obrócić siatkę w razie potrzeby, a następnie wykonać cięcie pionowe i obrócić ją z powrotem: w ten sposób nie musimy martwić się o dwa oddzielne przypadki cięć.
Złożoność: $O(n m)