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

ROBOCON - VOI 2012 Robocon

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/robocon


Cuộc thi vòng loại Robocon năm nay có chủ đề "Gặp gỡ". Các Robot sẽ tranh tài trên một lưới ô vuông gồm n hàng n cột. Các hàng của lưới được đánh số từ 1 đến n, từ trên xuống dưới. Các cột của lưới được đánh số từ 1 đến n, từ trái sang phải. Trên k ô vuông của lưới có đặt chướng ngại vật. Ở phần thi Robot tự động, mỗi đội sẽ phải sử dụng đồng thời hai con Robot.

Tại thời điểm xuất phát, Robot thứ nhất được đặt tại ô (1,1), mỗi bước chỉ được phép di chuyển sang ô kề cạnh bên phải, hoặc xuống ô kề cạnh bên dưới hoặc xuống ô kề đỉnh phía dưới bên phải.

Robot thứ hai được đặt tại ô (1,n), mỗi bước chỉ được phép di chuyển sang ô kề cạnh bên trái hoặc xuống ô kề cạnh bên dưới hoặc xuống ô kề đỉnh phía dưới bên trái.

Bắt đầu từ thời điểm xuất phát được tính là 0, hai Robot phải di chuyển liên tục theo qui tắc đã nêu. Thời gian di chuyển từ một ô sang ô kế tiếp được tính là 1 giây. Nhiệm vụ của đội chơi là phải lập trình điều khiển hai Robot xuất phát cùng lúc, di chuyển tránh chướng ngại vật để gặp nhau tại một ô vuông không có chướng ngại vật. Hai Robot gặp nhau càng sớm đội chơi càng được nhiều điểm. Lưới ô vuông được thiết kế đảm bảo là luôn có cách đi để hai Robot gặp được nhau.

Yêu cầu: Hãy tìm cách điều khiển sao cho hai Robot gặp nhau ở thời điểm sớm nhất.

Ràng buộc: 50% số tests ứng với 50% số điểm của bài có n ≤ 100.

Input

  • Dòng thứ nhất chứa hai số nguyên dương n, k (n ≤ 500, k ≤ 10000).
  • Dòng thứ i trong số k dòng tiếp theo chứa 2 số nguyên dương ui, vi tương ứng là tọa độ hàng và cột của ô có đặt chướng ngại vật (i = 1, 2, ..., k).

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

Output

Ghi ra một số nguyên dương là thời điểm sớm nhất tìm được.

Example

Input:
5 5
2 2
1 4
2 3
3 5
4 2 Output: 3

Được gửi lên bởi:VOJ Team
Ngày:2012-01-18
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:Tất cả ngoại trừ: ASM64 GOSU PERL6 PYPY RUST SED
Nguồn bài:VOI 2012

hide comments
2015-06-09 06:57:10 Stupid Dog
QHD + tham lam : 80
2014-12-25 03:51:58 Thắng Ðam Mê
bài này dùng BFS được ko
2014-12-06 15:28:24 livw


Last edit: 2015-01-06 18:37:51
2014-11-02 11:21:21 Hướng Thái Dương
bài này sử dụng pp loang khá hay :))
2014-09-26 13:05:44 [$Zeus$]
Robot phải di chuyển liên tục bạn nhé
2014-05-03 06:56:03 Trần Duy Lực
quy hoach dong cho bai nay :v
2014-02-21 15:24:07 Thcs Ðặng Chánh Kỷ
Cho mình hỏi là thời gian của 2 robot đi dến điểm gặp nhau có cần = nhau ko
2014-02-19 17:31:22 Anh Duc Le
Lúc đầu 15 quên mảng đánh dấu >> thêm mảng đánh dấu, lên 45.
Lại phát hiện nhầm mảng đánh dấu >> sửa tên biến , AC ^^
2013-10-28 16:08:35 a;slkfjasl;fkj
=))
2013-06-15 13:45:25 Nguyễn Thành Chinh
60đ rồi :D
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.