| 2019 IV Интеллектуальная олимпиада ПФО |
|---|
| Закончено |
Как-то раз, вскапывая огород на даче, Рудольф обнаружил в земле следы тёмной густой жидкости. Оказалось, что это — самая настоящая нефть! Более того, на огороде Рудольфа обнаружилось целых три её месторождения!
Предвкушая, что совсем скоро он сказочно разбогатеет, Рудольф принялся возводить на даче миниатюрный нефтепровод. Его цель — соединить все три месторождения трубами, чтобы можно было эффективно собирать ценный ресурс.
Дачные владения Рудольфа представляют собой прямоугольник размера $$$H \times W$$$, разделённый на участки размера $$$1 \times 1$$$. В трёх различных участках находятся нефтяные месторождения.
На некоторых участках можно прокладывать трубы. Стоимость прокладки труб на участках с месторождениями равна 0, а для других участков Рудольф оценил её величинами от 0 до 9. Существуют также непроходимые участки, на которых трубы прокладывать нельзя.
Рудольфу нужно проложить трубы так, чтобы от каждого месторождения нефти можно было добраться до других месторождений, перемещаясь исключительно по участкам, покрытым трубами и являющимся соседями. Два участка называются соседями, если они имеют общую сторону.
Помогите Рудольфу узнать минимальную стоимость строительства трубопровода.
Первая строка содержит целые числа $$$H$$$ и $$$W$$$ ($$$1 \le H, W \le 1000$$$) — размеры карты.
Следующие $$$H$$$ строк описывают карту. Каждая из них содержит $$$W$$$ символов $$$A_{ij}$$$ ($$$A_{ij} \in \left\{\texttt{0}-\texttt{9}, \texttt{X}, \texttt{*}\right\}$$$). Цифры обозначают стоимость прокладки трубопровода на соответствующем участке, символ $$$\texttt{X}$$$ — непроходимый участок, символ $$$\texttt{*}$$$ — участок с месторождением нефти.
Гарантируется, что карта содержит 3 месторождения.
Выведите одно целое число — минимальную стоимость соединения месторождений трубами.
Если соединить все три месторождения невозможно, выведите число -1.
5 7 XX*XX5X 2849063 375194* 44X4652 1*06472
33
2 5 *2X57 *6X4*
-1
В первом примере трубопровод можно проложить следующим образом (участки с трубами закрашены):
