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
2015-03-01 05:14:53 CK
Mình cũng chung cảnh ngộ 90.91 hoài mà ko biết chỗ nào fix. đổi bfs từ s->t thành t->s là 100 ngay :D

Last edit: 2015-03-01 06:32:59
2014-09-26 09:39:23 Dzui là chính dính là chui
bfs dùng tốt mà.có sao đâu.

Last edit: 2014-09-26 09:40:28
2014-09-23 07:17:14 Human Immunodeficiency Virus
== vãi cả các thánh xài bfs
2014-09-09 16:37:14 Bùi Quang Vinh
em làm có 90.91 @@ ... mà nó ko cho coi testcase nào sai thì đố mà biết cách mò
2014-08-13 19:02:35 ■■‡[ND] Bee Sociu■■‡
@@Khó chịu lắm hả [Try] . Ai 90.91 coi lại mảng hằng , AC rồi thì vào cảm ơn mình :))) hjhj
2014-07-20 14:45:09 [$Zeus$]
BFS nhá ae
2014-06-13 10:54:24 Thcs Ðặng Chánh Kỷ
BFS 1 cách khó chịu mới ac
2013-06-17 15:54:09 a;slkfjasl;fkj


Last edit: 2013-06-18 07:35:06
2013-05-23 08:08:31 a;slkfjasl;fkj
sửa lại đề rồi :))
2012-07-20 08:20:21 KAKALOT
hj
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.