KANDP - Mã và tốt

Tags: bfs, queue, graph

Problem

https://vn.spoj.com/problems/KANDP

https://oj.vnoi.info/problem/KANDP

Trên một bài cờ vua kích thước vô hạn có một con mã và một con tốt. Vị trí của quân mã là (Mx, My), vị trí của quân tốt là (Tx, Ty), trong đó x là chỉ số dòng và y là chỉ số cột. Quân mã được quyền đi theo 8 hướng như ở bàn cờ vua chuẩn. Quân tốt chỉ được đi một hướng là đi xuống dưới (từ vị trí (x, y) đến vị trí (x-1, y)). Hai quân cờ sẽ di chuyển theo lượt, xen kẽ nhau. Khi một quân cờ vào vị trí của quân cờ khác đang đứng thì quân cờ vừa di chuyển sẽ thắng.

Bạn biết vị trí ban đầu của hai quân cờ, quân cờ nào đi trước. Bạn hãy tính xem quân mã có khả năng thắng không và nếu thắng thì nó sẽ phải đi ít nhất là bao nhiêu nước.

Dữ liệu

  • Dòng thứ nhất ghi hai số Mx, My.
  • Dòng thứ hai ghi hai số Tx, Ty.
  • Dòng thứ ba ghi 0/1 ứng với quân mă đi trước hoặc quân tốt đi trước.

Kết quả

  • Dòng thứ nhất ghi YES/NO tương ứng với quân mă có khả năng thắng hoặc không có khả năng thắng.
  • Nếu dòng thứ nhất là YES thì dòng thứ hai ghi số bước ít nhất.

Giới hạn

Mx, My, Tx, Ty là các số nguyên có trị tuyệt đối nhỏ hơn hoặc bằng 1000. Trong 50% số test, Mx, My, Tx, Ty có trị tuyệt đối nhỏ hơn hoặc bằng 50.

Ví dụ

Input
0 0
0 3
0

Output
YES
2

Giải thích

Ở hình vẽ bên dưới, chữ K thể hiện vị trí quân mã, chữ P thể hiện vị trí quân tốt.


Tutorial


Submission

KANDP.cpp