trang chủ / đề bài / icpc20_nat_m

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 (x1,y1) và phải tìm đường tới vị trí đích (x2,y2).

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ừ (x,y) nó có thể đi tới (x,y+1), (x,y−1), (x−1,y) hoặc (x+1,y).

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ừ (1,1) tới (3,3), robot có thể đi theo đường (1,1)→(2,1)→(2,2)→(3,2)→(3,3), nhưng không thể đi theo đường (1,1)→(2,1)→(3,1)→(3,2)→(3,3) (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 T, số bộ dữ liệu (1≤T≤1000). Mỗi bộ dữ liệu nằm trên một dòng gồm 4 số nguyên x1,y1,x2,y2, 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á 109.

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ừ (x1,y1) tới (x2,y2).

Ràng buộc

  • 1≤T≤1000
  • |x1|,|y1|,|x2|,|y2|≤109

Ví dụ

Input Output Giải thích
2
1 1 3 3
0 1 1 1
4
1
Bộ thứ nhất: đường (1,1)→(2,1)→(2,2)→(3,2)→(3,3). 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

Không có bình luận tại thời điểm này.

gnatmake 12.2.0 a68g 3.1.2 nasm 2.16.1 as_x64 2.47 awk 1.3.4 gcc 16.2.0 dotnet 10.0.402 g++ 16.2.0 g++-themis 16.2.0 g++17 16.2.0 g++20 16.2.0 g++23 16.2.0 clang++ 22.1.8 dmd 2.113.0 dart 3.13.6 gforth 0.7.3 gfortran 15.3.0 go 1.27.3 groovyc 5.1.3 javac 26.0.2.1 node 26.12.1 julia 1.13.2 kotlinc 2.4.21 lean 4.35.0 sbcl 2.2.9 lua 5.5.1 nim 2.2.12 fpc 3.2.2 fpc-themis 3.2.2 perl 5.42.3 php 8.5.12 pike 8.0 swipl 9.0.4 pypy3 7.3.23 python3 3.15.1 racket 8.7 ruby 4.0.8 rustc 1.99.1 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 swiftc 6.4.1 tclsh 8.6 bun 1.4.4 deno 2.9.8 v 0.5.2 zig 0.17.0