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.|

QBBISHOP - VOI06 Quân tượng

Hiện tại, bài tập này đã có trên online judge chính thức của VNOI, bạn có thể truy cập ở đây: https://oj.vnoi.info/problem/qbbishop


Xét bàn cờ vuông kích thước n×n. Các dòng được đánh số từ 1 đến n, từ dưới lên trên. Các cột được đánh số từ 1 đến n từ trái qua phải.

Ô nằm trên giao của dòng i và cột j được gọi là ô (i,j). Trên bàn cờ có m (0 ≤ m ≤ n) quân cờ. Với m > 0, quân cờ thứ i ở ô (ri, ci), i = 1,2,..., m. Không có hai quân cờ nào ở trên cùng một ô. Trong số các ô còn lại của bàn cờ, tại ô (p, q) có một quân tượng. Mỗi một nước đi, từ vị trí đang đứng quân tượng chỉ có thể di chuyển đến được những ô trên cùng đường chéo với nó mà trên đường đi không phải qua các ô đã có quân

Cần phải đưa quân tượng từ ô xuất phát (p, q) về ô đích (s,t). Giả thiết là ở ô đích không có quân cờ. Nếu ngoài quân tượng không có quân nào khác trên bàn cờ thì chỉ có 2 trường hợp: hoặc là không thể tới được ô đích, hoặc là tới được sau không quá 2 nước đi (hình trái). Khi trên bàn cờ còn có các quân cờ khác, vấn đề sẽ không còn đơn giản như vậy.

Yêu cầu: Cho kích thước bàn cờ n, số quân cờ hiện có trên bàn cờ m và vị trí của chúng, ô xuất phát và ô đích của quân tượng. Hãy xác định số nước đi ít nhất cần thực hiện để đưa quân tượng về ô đích hoặc đưa ra số -1 nếu điều này không thể thực hiện được.

Input

Dòng đầu tiên chứa 6 số nguyên n, m, p, q, s, t.

Nếu m > 0 thì mỗi dòng thứ i trong m dòng tiếp theo chứa một cặp số nguyên ri , ci xác định vị trí quân thứ i.

Hai số liên tiếp trên cùng một dòng được ghi cách nhau ít nhất một dấu cách.

Output

Gồm 1 dòng duy nhất là số nước đi tìm được

Example

Input:
8 3 7 2 1 4
5 4
3 4
4 7

Output:
3

Hạn chế:

Trong tất cả các test: 1 ≤ n ≤ 200. Có 60% số lượng test với n ≤ 20.


Được gửi lên bởi:special_one
Ngày:2008-09-25
Thời gian chạy:0.200s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:Tất cả ngoại trừ: ERL GOSU JS-RHINO NODEJS PERL6 PYPY RUST SED VB.NET
Nguồn bài:Vietnam Olympiad of Informatics 2006 - Bảng B

hide comments
2019-11-27 09:33:33
81.83 la quen -1 nha :>
2019-08-31 08:58:37
bằng 1 cách nào đó test đề bài ra 3 nhưng code của mình ra 4 =)) bằng 1 cách chày cối nào đó mình vẫn cố sub nhưng vẫn AC =))
https://ideone.com/uUY94J
2019-08-01 03:49:20
Dijkstra AC :))
2018-12-07 18:10:59
code sai cũng AC :v
test
8 3 7 2 8 5
5 4
3 4
4 7
mình ra 3 nhưng thực ra kết quả là 2 ^^
2018-06-07 15:43:55
xàm nồi 3 đấm ms ac :v
2018-04-06 11:09:34
quên cout<<-1; mất 8 đấm :vv
2018-03-20 17:34:50
63.64
2017-09-25 10:42:32
1 đấm AC :) cda.dev
2017-08-25 06:28:52
Kham khảo code
https://vietcodes.github.io/code/58/
2017-08-03 18:44:56
how to fix từ 90.91 lên 100, các cao nhân chỉ e với :(((
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.