Стіна підземелля#3544
У 2337 році люди відчувають нудьгу у повсякденному житті та прагнуть отримати незабутні враження. Сьогодні "Пригода в підземеллі" — одна з найпопулярніших атракцій, де відважні авантюристи ризикують життям, щоб знищити злих монстрів і врятувати світ.
Ви керуєте таким підземеллям. Останнім часом ви отримали багато скарг від солдатів, які часто відвідують ваше підземелля; вони стверджують, що воно занадто легке, і не хочуть повертатися. Ви розглядаєте можливість ускладнити підземелля, збільшивши відстань між входом і виходом, щоб більше монстрів могли атакувати авантюристів.
Ваше підземелля має форму прямокутника з шириною і висотою . Це сітка, що складається з W \times H квадратних кімнат розміром 1 \times 1. Південно-західний кут підземелля має координати , а північно-східний кут — (W, H). Зовні підземелля оточене стінами, і всередині можуть бути додаткові стіни, щоб перешкодити авантюристам швидко дістатися до виходу. Кожна стіна в підземеллі паралельна або осі , або осі , і її обидва кінці знаходяться на цілих координатах. Авантюрист може рухатися з однієї кімнати в іншу, якщо вони суміжні вертикально або горизонтально і між ними немає стіни.
Ви хочете додати стіну, щоб збільшити довжину найкоротшого шляху між входом і виходом. Однак через фінансові обмеження ви можете побудувати не більше однієї стіни довжиною в одну одиницю. Зверніть увагу, що нова стіна також повинна відповідати зазначеним вище обмеженням. Крім того, ви повинні гарантувати, що є принаймні один шлях від входу до виходу.
Ваша задача — визначити, де розмістити нову стіну, щоб максимізувати мінімальну кількість кроків між входом і виходом. Чи зможете ви це визначити?
Перший рядок містить три цілі числа , і (1 \leq W, H \leq 50, 0 \leq N \leq 1000), розділені пробілом.
Наступні рядків містять опис внутрішніх стін. Кожен із цих рядків містить чотири цілі числа sx_i, sy_i, dx_i, dy_i — координати кінців -ї стіни, проведеної від (sx_i, sy_i) до (dx_i, dy_i) (включно).
Останні два рядки задають вхід і вихід. Перший з них містить два цілі числа і ; другий — два цілі числа і . Вхід знаходиться в кімнаті з південно-західним кутом (ix, iy), а вихід — у кімнаті з південно-західним кутом (ox, oy).
Виведіть максимальне можливе збільшення мінімальної кількості необхідних кроків між входом і виходом лише шляхом додавання однієї стіни. Якщо немає хорошого місця для побудови нової стіни, виведіть 0.
Приклад 1