Дивний кінь
Limits: 2 sec., 512 MiB
Вінниця. Ніч. Дивний кінь ходить по гуртожитку Вінницького національного технічного університету.
Гуртожиток представляє собою квадрат розміром \(n\times n\), який складається з \(n^2\) квадратних кімнат розміром \(1 \times 1\). Верхня ліва кімната має координати \((1, 1)\), нижня права — \((n, n)\). Кінь сумує і тому хоче завітати до кімнати своїх друзів. Однак злі вахтери хочуть не дозволити йому це зробити. Усі вони сидять у різних кімнатах, і жоден із них не є в кімнаті, де зараз стоїть кінь. Якщо після свого ходу кінь опиниться в одній кімнаті з вахтером, то наш герой буде вигнаний з гуртожитку. Проте, якщо протягом свого ходу кінь проскакував через кімнату з вахтером, той не міг стримати страху і покидав свою роботу.
Оскільки кінь дуже хоче побачити своїх друзів, то він хоче дійти до їхньої кімнати за мінімальну кількість ходів.
Input
У першому рядку задано два цілі числа \(n\) і \(k\) — довжина гуртожитку й кількість вахтерів у ньому відповідно.
У другому рядку задано два цілих числа \(sx\), \(sy\) — координати кімнати, де початково стоїть кінь.
У третьому рядку задано два цілих числа \(fx\), \(fy\) — координати кімнати, де є друзі коня (координати кімнати можуть збігатися з координатами кімнати коня).
У наступних \(k\) рядках задано по два цілих числа \(x_i\), \(y_i\) — координати кімнат, де сидять вахтери.
Output
Якщо кінь зможе дістатися до кімнати друзів, то виведіть одне ціле число — мінімальну кількість кроків, які йому необхідно для цього.
Інакше виведіть число -1
.
Constraints
\(1 \le n \le 50\),
\(0 \le k \le 10\),
\(1 \le sx, sy, fx, fy, x_i, y_i \le n\).
Samples
Input (stdin) | Output (stdout) |
---|---|
3 0 1 1 3 2 | 1 |
Input (stdin) | Output (stdout) |
---|---|
3 1 1 1 3 2 3 2 | 5 |
Input (stdin) | Output (stdout) |
---|---|
3 0 1 1 3 3 | 4 |
Input (stdin) | Output (stdout) |
---|---|
3 2 1 1 3 3 3 2 2 3 | -1 |
Submit a solution
Element Type | Created | Who | Problem | Compiler | Result | Time (sec.) | Memory (MiB) | # | Actions |
---|
Element Type | Created | Who | Problem | Compiler | Result | Time (sec.) | Memory (MiB) | # | Actions |
---|