Республиканская олимпиада по информатике 2009 год


Задача F. Физкультура

Ограничение по времени:
2 секунды
Ограничение по памяти:
256 мегабайт

В список предметных олимпиад школьников решили, наконец, внести и физкультуру. Оргкомитет должен подготовить маршрут, по которому будет проводиться соревнование по бегу. Для проведения соревнований была выделена прямоугольная территория, которую для удобства разделили на квадраты так, что получилась сетка $N \times M$. Для каждого квадрата была определена стоимость его подготовки к соревнованиям. Также были определены квадраты, в которых должен начинаться и оканчиваться маршрут. Маршрутом будем считать такую последовательность квадратов, что каждые два соседних квадрата в этой последовательности имеют общую сторону. Ваша задача — помочь оргкомитету выбрать маршрут так, чтобы стоимость подготовки его к соревнованиям была минимально возможной.
Формат входного файла
Первая строка входного файла содержит два целых числа: $N$ и $M$ ($1 \le N, M \le 200$) — размеры территории. Каждая из следующих $N$ строк содержит по $M$ целых чисел в пределах от $1$ до $100$ — стоимость подготовки соответствующего квадрата к соревнованиям. Следующая строка содержит $2$ целых числа — номер строки и столбца для квадрата, в котором должен начинаться маршрут. Следующая строка содержит $2$ целых числа — номер строки и столбца для квадрата, в котором должен заканчиваться маршрут. Маршрут начинается и заканчивается в разных квадратах. Числа в строках разделены пробелами.
Формат выходного файла
На первой строке выходного файла выведите наименьшую суммарную стоимость подготовки маршрута, а на следующих строках — карту маршрута. Карта маршрута — это таблица размера $N \times M$, в $j$-м столбце $i$-й строки которой расположен $0$, если через соответствующих квадрат не проходит ни один маршрут, и $1$, если через него проходит маршрут. Если оптимальных ответов несколько, то выведите любой. Числа в строках разделяйте пробелом.
Пример:
Вход
3 3
1 1 1
1 1 1
10 1 1
1 1
3 3
Ответ
5
1 0 0
1 1 0
0 1 1
посмотреть в олимпиаде

Комментарий/решение: