| Nộp bài | Các bài nộp | Làm tốt nhất | Về danh sách bài |
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; −103 ≤ xi, yi ≤ 103 )
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: | adm |
| 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 PERL PERL6 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 <(") |
