Three States
Contest: Codeforces Round 327 (Div. 1)
Difficulty rating: 2200
Tags: dfs and similar, graphs, shortest paths

The famous global economic crisis is approaching rapidly, so the states of Berman, Berance and Bertaly formed an alliance and allowed the residents of all member states to freely pass through the territory of any of them. In addition, it was decided that a road between the states should be built to guarantee so that one could any point of any country can be reached from any point of any other State.

Since roads are always expensive, the governments of the states of the newly formed alliance asked you to help them assess the costs. To do this, you have been issued a map that can be represented as a rectangle table consisting of n rows and m columns. Any cell of the map either belongs to one of three states, or is an area where it is allowed to build a road, or is an area where the construction of the road is not allowed. A cell is called passable, if it belongs to one of the states, or the road was built in this cell. From any passable cells you can move up, down, right and left, if the cell that corresponds to the movement exists and is passable.

Your task is to construct a road inside a minimum number of cells, so that it would be possible to get from any cell of any state to any cell of any other state using only passable cells.

It is guaranteed that initially it is possible to reach any cell of any state from any cell of this state, moving only along its cells. It is also guaranteed that for any state there is at least one cell that belongs to it.

Input format:
The first line of the input contains the dimensions of the map n and m (1 ≤ n, m ≤ 1000) — the number of rows and columns respectively.

Each of the next n lines contain m characters, describing the rows of the map. Digits from 1 to 3 represent the accessory to the corresponding state. The character '.' corresponds to the cell where it is allowed to build a road and the character '#' means no construction is allowed in this cell.

Output format:
Print a single integer — the minimum number of cells you need to build a road inside in order to connect all the cells of all states. If such a goal is unachievable, print -1.

Constraints:
Time limit: 5.0 s
Memory limit: 512.0 MB

Example input:
4 5
11..2
#..22
#.323
.#333

Example output:
2

Example input:
1 5
1#2#3

Example output:
-1

Editorial:
Утверждение. В неориентированном невзвешенном связном графе с тремя выделенными вершинами кратчайшая сеть, связывающая выделенные вершины, выглядит как некоторая вершина графа, возможно выделенная, из которой исходят кратчайшие пути к каждой из выделенных вершин, причём эти пути являются вершинно-непересекающимися.
Доказательство. Назовём выделенные вершины A, B и C. Рассмотрим пути из вершины A в вершины B и C, принадлежащие кратчайшей связывающей сети. Каждый из этих путей является простым, т. е. не проходящим через любую вершину больше одного раза, т. к. сеть является кратчайшей. Рассмотрим последнюю общую вершину этих путей — пусть это вершина D. Заметим, что части обоих путей от вершины A до вершины D полностью совпадают, т. к. если они не совпадают, можно заменить обе части на какую-нибудь одну из них, что уменьшит длину связывающей сети. Получили, что оптимальная сеть состоит из вершины D, из которой исходят вершинно-непересекающиеся пути к каждой из трёх выделенных вершин. Теперь длина кратчайшей сети — это сумма длин путей от вершины D до трёх выделенных вершин, поэтому ясно, что эти пути нужно взять кратчайшими. Утверждение доказано.
Теперь имеем следующий метод для нахождения длины кратчайшей связывающей сети: перебрать все вершины, включая выделенные, и из сумм кратчайших расстояний от данной вершины до выделенных выбрать минимальную. Ясно, что таким образом мы переберём длины различных связывающих сетей, среди которых будет и длина кратчайшей, и поэтому минимум будет ответом.
Теперь заметим, что для сведения исходной задачи к задаче поиска длины кратчайшей связывающей сети, можно представить карту в виде графа, где вершинам соответствуют клетки, а ребро между двумя вершинами ставится, если они являются соседними. В этом графе теперь нужно все вершины, соответствующие некоторому государству, объединить в одну, множество рёбер которой будет представлять собой объединение множеств рёбер изначальных вершин этого государства. Несложно заметить, что исходная задача таким образом свелась к вышеописанной.