eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Місце зустічі змінити неможна

Місце зустічі змінити неможна

Добрі друзі Петя та Вася вирішили пограти у жмурки в лабіринті. Через декілька голин гри їм стало нудно і вони вирішили знайти один одного якомога раіьше. Лабіринт має форму прямокутника і розбитий на \textbf{N}×\textbf{M} клітинок, у кожній з яких або стінка, або прохід. Петя та Вася можуть переходити з однієї клітинки у іншу, якщо у клітинок є спільна сторона. Не дозволяється відвідувати клітинки, у яких стоїть стінка. Хлопчики можуть ходити одночасно. Необхідно знайти клітинку, у якій можуть зустрітится Вася та Петя через мінімально можливу кількість ходів. \InputFile У першому рядку \textbf{1} ≤ \textbf{N}, \textbf{M} ≤ \textbf{100} - розміри лабіринту. Далі \textbf{4} натуральних числа \textbf{P_x}, \textbf{P_y}, \textbf{V_x}, \textbf{V_y} - координати клітинок, у яких знаходяться Петя та Вася відповідно. Гарантується, що у початковий момент часу хлопчики не знаходяться у клітинках, які зайняті стінкою (\textbf{P_x}, \textbf{V_x} - номер рядка, \textbf{P_y}, \textbf{V_y} - номер стовбця). Далі \textbf{N} рядків по \textbf{M} чисел у кожному, які описують лабіринт, \textbf{1} - якщо у даній клітинці стоїть стіна, \textbf{0} - інакше. \OutputFile У першому рядку два натуральних числа \textbf{X_m}, \textbf{Y_m} - координати клітинки, у якій вони зустрінуться. Якщо вони не зможуть зустрітися, то у вихідний файл потрібно вивести \textbf{-1}. Якщо розв'язків декілька - виведіть довільний.
Ліміт часу 1 секунда
Ліміт використання пам'яті 64 MiB
Вхідні дані #1
4 3
1 2
3 1
1 0 1
1 0 0
0 1 0
0 0 0
Вихідні дані #1
3 3