Robot trục trặc
Đề bài
Mô tả
Arthur tham gia Olympic Robot Việt Nam 2020. Ở vòng đầu tiên, mỗi thí sinh phải chế tạo một robot tìm đường. Cụ thể, ban tổ chức đã chuẩn bị một lưới vô hạn không có vật cản. Robot của một thí sinh được đặt tại vị trí xuất phát và phải tìm đường tới vị trí đích .
Robot của Arthur khá đơn giản: nó chỉ di chuyển được theo bốn hướng lên, xuống, trái, phải, tức là từ nó có thể đi tới , , hoặc .
Vòng đầu sắp bắt đầu thì Arthur phát hiện một số linh kiện của robot bị hỏng, nên robot không thể đi cùng một hướng ở hai bước liên tiếp (tức là sau mỗi bước, nó luôn phải đổi hướng). Ví dụ, để đi từ tới , robot có thể đi theo đường , nhưng không thể đi theo đường (hai bước đầu cùng sang phải).
Hãy giúp Arthur tìm số bước di chuyển ít nhất để robot đi từ vị trí xuất phát tới vị trí đích.
Dữ liệu vào
Dòng đầu tiên chứa số nguyên , số bộ dữ liệu (). Mỗi bộ dữ liệu nằm trên một dòng gồm số nguyên , lần lượt là vị trí xuất phát và vị trí đích của robot.
Giá trị tuyệt đối của mọi số nguyên trong dữ liệu vào không vượt quá .
Dữ liệu ra
Với mỗi bộ dữ liệu, in ra số bước di chuyển ít nhất để robot đi từ tới .
Ràng buộc
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 2 1 1 3 3 0 1 1 1 |
4 1 |
Bộ thứ nhất: đường . Bộ thứ hai: một bước sang phải. |
| 3 0 0 0 2 0 0 0 3 2 -1 2 -1 |
4 5 0 |
Ví dụ bổ sung (không có trong đề gốc). Bộ thứ nhất: lên, phải, lên, trái. Bộ thứ hai: lên, phải, lên, trái, lên. Bộ thứ ba: robot đã ở đích. |
Bình luận