Editorial for MOVE - Tí chơi cờ
Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.
Submitting an official solution before solving the problem yourself is a bannable offence.
Ta nhận xét rằng, sau mỗi bước di chuyển thì tính chẵn lẽ của tọa độ quân cờ ~A~ không đổi. Do đó:
- Nếu ~|x_2 −x_1|~ lẻ, hoặc ~|y_2 −y_1|~ lẻ thì không có cách để di chuyển quân cờ ~A~ từ ô ~(x_1,y_1)~ đến ô ~(x_2,y_2)~.
- Ngược lại, ta cần mất ~\frac{|x_2-x_1|}{2}~ bước để di chuyển quân cờ ~A~ từ ô ~(x_1,y_1)~ đến ô ~(x_2,y_1)~, và mất ~\frac{|y_2-y_1|}{2}~ bước để di chuyển quân cờ ~A~ từ ô ~(x_2,y_1)~ đến ô ~(x_2,y_2)~. Do đó, đáp án là:
$$\frac{|x_2-x_1| + |y_2-y_1|}{2}$$
Độ phức tạp: ~O(1)~
Comments