Connect the Points
By Gabriel Dalalio, ITA 
Brazil
By Gabriel Dalalio, ITA Brazil
I'll give you a challenge! You will receive an array of size N by M, with the characters '-', '#' and '*'. See an example below:
*-#-*
-----
--*--
####-
*----
The character '#' means obstacles, the characters '-' mean empty spaces and the characters '*' mean points. Your job is to put the minimum amount of additional points needed to make all points connected. You can only put more points in empty spaces. For example, for the matrix above, you need at least 7 additional points to connect all the points, as shown in the following figure:
*-#-*
-*-*-
--*-*
####*
****-
Do you accept the challenge?
The input contains several test cases. Each test case starts with a line containing two integers N and M indicating the dimensions of the matrix (1 ≤ N*M ≤ 100). After the first line, the next N lines describe the array in the same manner shown in the statement.
For each test, the output consists of one line containing the minimum number of additional points that need to be added to the matrix to connect all the points. If it is impossible to connect all the points, print 'impossivel'.
| Sample Input | Sample Output |
|
5 5
*-#-* 3 4 ---* ---- *--- 1 5 *-#-* 2 2 -# #- |
7 2 impossivel 0 |