Республиканская олимпиада по информатике 2009 года за 9 класс | Казахстанские олимпиады

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

В список предметных олимпиад школьников решили, наконец, внести и физкультуру. Оргкомитет должен подготовить маршрут, по которому будет проводиться соревнование по бегу. Для проведения соревнований была выделена прямоугольная территория, которую для удобства разделили на квадраты так, что получилась сетка $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