— Здравствуйте! Могу я поговорить с Петровым? Алё, милый, привет… ты знаешь, у нас дома небольшая авария произошла… Но твой компьютер не пострадал, не волнуйся. Но теперь там немного грязно. Ну, то есть очень грязно. Но ты не волнуйся, я приготовила тебе твои болотные сапоги, у входа стоят. А грязь я уберу, как будет свободное время. Когда? Ну, наверное, когда в отпуск пойду. А, ну когда вернёмся из Турции. А, ну значит в следующий отпуск, но обязательно уберу. А пока я у мамы поживу. И ты, кстати, тоже можешь. Ну, как хочешь, я же не заставляю… Только пока я не убрала, ты там грязь не разводи, сильно сапогами по грязи не шлёпай и когда по чистому ходишь, сапоги снимай и тапочки обувай, я их тоже возле входа поставила, ты их бери с собой, когда идёшь по грязи и переобувай. А когда по чистому идёшь, бери сапоги, там грязь в разных местах.
Программисты, как известно, не самые трудолюбивые люди, поэтому убирать грязь не станут. Но переобувать болотные сапоги каждый раз, когда переходишь от грязного пола к чистому и наоборот — удовольствие ниже среднего, уж лучше пройти лишние несколько метров. Чтобы прожить время до следующего отпуска с комфортом, надо срочно выработать способ добираться из одной точки квартиры с минимальным количеством переобуваний по пути, ну а уж среди них, конечно, выбрать самый короткий.
Для начала, естественно, задаться нахождением способа оптимального прохождения Самого Главного Пути — от компьютера до холодильника.
Исходные данные
В первой строке записаны целые числа N и M — размеры квартиры (1 ≤ N, M ≤ 500). Два целых числа во второй строке — координаты компьютера, а два целых числа в третьей строке — координаты холодильника. Далее идут N строк по M символов в каждой — план квартиры. На плане 1 означает чистое место, 2 — грязное, 0 — стена или непроходимая грязь. Переходить можно только на клетки, имеющие общую вершину с данной, при переходе с чистой на грязную и наоборот надо переобуваться. Холодильник и компьютер находятся не в клетках, помеченных нулём.
Левая верхняя клетка плана имеет координаты (1, 1).
Результат
Выведите длину кратчайшего пути (количество преодоленных квадратиков, включая начальный и конечный) с минимальным количеством переобуваний и количество переобуваний (переобувание проходит при переходе с грязного на чистое и наоборот). Если пройти к холодильнику невозможно, выведите числа 0 0.
Примеры
исходные данные | результат |
---|
3 7
1 1
3 7
1200121
1212020
1112021 | 8 4 |
5 5
1 5
5 1
00001
00000
00000
00000
20000
| 0 0 |
Автор задачи: Идея — Станислав Васильев, подготовка — Станислав Васильев, Павел Егоров
Источник задачи: VIII Командный студенческий чемпионат Урала по программированию. Екатеринбург, 11-16 марта 2004 г.