Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

PTIT017K - ACM PTIT 2017 K - QUÂN MÃ

Xét lưới ô vuông vô hạn trong đó có một số ô cấm, các ô còn lại là tự do. Các dòng và cột của lưới được đánh số theo thứ tự bởi các số nguyên … -3 -2 -1 0 1 2 3 … Các cột được đánh số theo thứ tự từ trái sang phải, còn các dòng theo thứ tự từ dưới lên trên. Ô nằm trên giao của dòng x và cột y được gọi là ô (x, y). Một quân mã  đặt ở ô xuất phát là ô (0,0). Sau một bước đi, ta có thể di quân mã đến một trong các ô ở đỉnh đối diện trên đường chéo của hình chữ nhật kích thước 2×3.

 

 

 

 

 

 

 

 

 

  X

 

  X 

 

 

 

  X

 

 

  

  X

 

 

 

 

  M

 

 

 

 

  X

 

 

 

  X

 

 

 

  X

 

  X

 

 

 

 

 

 

 

 

 

Luật di chuyển của quân mã

Yêu cầu: Cho biết toạ độ của các ô cấm, vị trí ô đích nơi quân mã cần đến, hãy tìm cách di chuyển quân mã từ ô (0,0) đến ô đích sao cho số lượng bước đi cần thực hiện là ít nhất.

Input

Dòng đầu tiên chứa T (T ≤ 3) là số lượng test, tiếp đến là T nhóm dòng, mỗi nhóm chứa dữ liệu về một test theo khuôn dạng sau:

  • Dòng đầu tiên chứa 2 số nguyên xt, yt được ghi cách nhau bởi dấu cách cho biết toạ độ của ô đích là (xt, yt);
  • Dòng thứ hai chứa số nguyên dương n (n ≤ 1000) là số lượng ô cấm;
  • Dòng thứ i trong số n dòng tiếp theo chứa hai số nguyên được ghi cách nhau bởi dấu cách xi, yi cho biết (xi, yi) là toạ độ của ô cấm thứ i (i = 1, 2, …, n).

Chú ý : (−103 xt, yt ≤ 103;  −103xi, yi ≤ 10)

Output

Gồm T dòng mỗi dòng chứa kết quả của một test tương ứng trong dữ liệu vào là số lượng bước đi ít nhất cần thực hiện để di chuyển quân mã từ ô xuất phát (0,0) đến ô đích. Ghi số −1 nếu như không thể di chuyển quân mã đến ô đích. 

Example

Input:
1
2 4
0 Output: 2

Được gửi lên bởi:Admin
Ngày:2017-04-29
Thời gian chạy:1s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:ASM32-GCC ASM32 ASM64 MAWK BC C CSHARP C++ 4.3.2 CPP CPP14 COFFEE LISP sbcl DART FORTH GO JAVA JS-RHINO JS-MONKEY KTLN OCT PAS-GPC PAS-FPC PERL6 PERL PROLOG PYTHON PYTHON3 PY_NBC R RACKET SQLITE SWIFT UNLAMBDA

hide comments
2017-07-31 04:37:32
Test có vẻ hơi mềm .___.
Với bộ input
"3
6 3 8
5 1
5 5
4 2
4 4
7 1
7 5
8 2
8 4"
tổng thể em mất 1.46s, vậy mà sub lên thì tổng thời gian chạy các test 0.01 <(")
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.