Đầu tiên ta sẽ loại bỏ hết các hàng và cột không có quái vật nào vì chúng không quan trọng trong bài này.

Gọi \(X\) và \(Y\) là số hàng và cột có quái vật \((1 \leq X \leq N, 1 \leq Y \leq M)\).

Ta ánh xạ một cách tô màu với một đường đi từ ô \((0, 0)\) đến ô \((X, Y)\) như sau:

Xuất phát tại ô \((0, 0)\), tại một thời điểm mà ta đang đứng ở ô \((x, y)\), ta đi sang ô \((x + 1, y)\) nếu ô \((x + 1, y)\) là ô cuối cùng có màu của hàng \(x + 1\), nếu không ta đi sang ô \((x, y + 1)\), và ô \((x, y + 1)\) là ô cuối cùng có màu của cột \(y + 1\) (vì nếu cả hai không phải ô cuối cùng thì ô \((x + 1, y + 1)\) sẽ có màu của cả hàng \(x + 1\) và cột \(y + 1\)).

Ánh xạ là đơn ánh vì với mỗi cách tô màu, ta có một và chỉ một cách đi. Ánh xạ là toàn ánh vì với mỗi cách đi ta chỉ có một cách tô màu. Cách biến đổi từ đường đi về một cách tô màu như sau:

Giả sử ta đang đứng tại vị trí \((x, y)\). Nếu tại lượt sau ta đi sang ô \((x + 1, y)\) thì ô này phải là ô cuối cùng có màu của hàng \(x + 1\). Ta tô các ô từ \((x + 1, 1)\) đến \((x + 1, y)\) bằng màu của hàng \(x + 1\), sau đó tiếp tục làm tiếp. Khi đến một ô \((x, y)\), ta đã tô màu cả bảng từ \((1, 1)\) đến \((x, y)\) nên sau khi làm xong tất cả các ô đều được tô màu.

Vậy ánh xạ là song ánh, suy ra số cách tô màu bằng số đường đi từ ô \((0, 0)\) đến ô \((X, Y)\) hay \(\binom{X + Y}{X}\).

Ở dưới là một ví dụ về ánh xạ giữa cách tô màu và đường đi:

Độ phức tạp: \(O(N \log N)\) hoặc \(O(N)\) tùy vào cách cài đặt.