ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила

1325. Грязь

Ограничение времени: 0.5 секунды
Ограничение памяти: 64 МБ
— Здравствуйте! Могу я поговорить с Петровым? Алё, милый, привет… ты знаешь, у нас дома небольшая авария произошла… Но твой компьютер не пострадал, не волнуйся. Но теперь там немного грязно. Ну, то есть очень грязно. Но ты не волнуйся, я приготовила тебе твои болотные сапоги, у входа стоят. А грязь я уберу, как будет свободное время. Когда? Ну, наверное, когда в отпуск пойду. А, ну когда вернёмся из Турции. А, ну значит в следующий отпуск, но обязательно уберу. А пока я у мамы поживу. И ты, кстати, тоже можешь. Ну, как хочешь, я же не заставляю… Только пока я не убрала, ты там грязь не разводи, сильно сапогами по грязи не шлёпай и когда по чистому ходишь, сапоги снимай и тапочки обувай, я их тоже возле входа поставила, ты их бери с собой, когда идёшь по грязи и переобувай. А когда по чистому идёшь, бери сапоги, там грязь в разных местах.
Программисты, как известно, не самые трудолюбивые люди, поэтому убирать грязь не станут. Но переобувать болотные сапоги каждый раз, когда переходишь от грязного пола к чистому и наоборот — удовольствие ниже среднего, уж лучше пройти лишние несколько метров. Чтобы прожить время до следующего отпуска с комфортом, надо срочно выработать способ добираться из одной точки квартиры с минимальным количеством переобуваний по пути, ну а уж среди них, конечно, выбрать самый короткий.
Для начала, естественно, задаться нахождением способа оптимального прохождения Самого Главного Пути — от компьютера до холодильника.

Исходные данные

В первой строке записаны целые числа 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 г.