Link Sub: http://www.spoj.com/PTIT/problems/P142PROC/
Người Gửi: Dương Lee
- Problem:
Tèo đang học cách chơi cờ với một bàn cờ kích thước 8x8. Cậu ấy đang học cách đi của quân xe, tượng và vua. + Quân tượng đi theo đường chéo, tùy ý số lượng ô.
+ Quân xe thì đi theo chiều dọc hoặc ngang, cũng tùy ý số lượng ô.
+ Quân vua thì đ itheo được 8 hướng nhưng mỗi lần chỉ đi được 1 ô.
Và tất cả quân này khi gặp vật cản hay cạnh bàn cờ thì đều không đi được tiếp. Tèo đang thắc mắc, với mỗi quân cờ tượng, xe, vua thì sẽ mất ít nhất bao nhiều bước để di chuyển giữa 2 ô cho trước.
Input
Gồm một dòng duy nhất gồm 4 số nguyên là tọa độ của 2 ô cờ r1,c1, r2, c2 (1<=r1,c1,r2,c2<=8).
Output
Gồm 3 số nguyên lần lượt là số bước đi ít nhất của quân xe, tượng, vua. Trường hợp nào không đi được thì in ra số 0.
Example:
Gồm 3 số nguyên lần lượt là số bước đi ít nhất của quân xe, tượng, vua. Trường hợp nào không đi được thì in ra số 0.
Input
4 3 1 6
Output:
2 1 3
Input
5 5 5 6
Output:
1 0 1
- Solution:
Các bước làm:
- Ghi các đỉnh theo thứ tự từ trái qua phải, trên xuống dưới (dinh[][])
- Tạo danh sách liên kiết các đỉnh theo các bước đi cho các quân cơ trên bàn cờ (vector Xe[], vector Vua[], vector Tinh[]).
- Khởi tạo mảng đánh dấu và mảng dấu vết.
- Duyệt BFS_queue: với từng trường hợp quân và đồng thời dấu vết để đánh dấu các bước đi.
in ra bước đi di chuyểnInput
5 5 5 6
Output:
1 0 1