Spoiler Alert

Hint 1

• Đề yêu cầu ta đi nhiều đường chéo nhất có thể

Ta sẽ đi theo đường zigzag và đi sang biên nếu không

Hint 2

• Cách đi tốt nhất là ta đi zigzag, và gần ô kết thúc thì ta sẽ đi sang cạnh kề

\(\Rightarrow max(n, m)\) là đường đi xa nhất

\(\Rightarrow\) khi \(k < max(n, m)\) thì không đi được

\(\Rightarrow\) khi \(k > max(n, m)\) thì ta đi zigzag qua lại gần ô kết thúc trước khi đi vào

Hint 3

• Tô màu bảng trên gồm các màu trắng - đen xen kẽ nhau, không hai ô chung cạnh cùng màu

Khi ta di chuyển zigzag thì các ô đó sẽ cùng màu

Hint 4

• Nếu 2 ô đầu và kết thúc cùng màu thì

Nếu số bước đi \(k\) và \(max(n, m)\) cùng tính chẵn lẻ. Thì ta cứ đi zigzag qua lại ô kết thúc

Nếu số bước đi \(k\) và \(max(n, m)\) không cùng chẵn lẻ. Thì khi cuối cùng sẽ đi sang biên 2 lần để đến ô kết thúc

• Nếu 2 ô đầu và kết thúc khác màu thì

Chúng ta chỉ cần đi zigzag qua lại kề biên với điểm kết thúc, và bước cuối ta đi sang biên tới ô kết thúc