Best Place to Arrange Contest

subhashis_cse 7th CPU CSE Programming C...
Limits 1s, 512 MB

We are going to arrange the 7th CPU CSE programming contest in our department. But to arrange a contest we are already facing some difficulties. There are also a lot of programmers joining from different places.

So the judge panel is discussing the place &  trying to select a place which is optimal. Since there are some problems, the judge panel needs your help.

Here optimal means that the total travel cost from the contest place & the contestant resident need to be minimum.

That's why you are given a grid of n*m size, where the grid cell contains 0,1or 2.

Here 0 indicates the place where you can arrange a contest.

1 indicates where the contestants are staying and this contestant can not pass through another contestant also.

2 indicates that there are some problems in that place and any contestant can not pass through this cell.

So you want to choose a contest place where you can arrange a contest  such that total travel cost is minimum from all the contestant’s staying place.

You can only go up, down, left & right from any place.

Return the total minimum travel cost for such a contest place. If it's not possible to host a contest then you need to return -1.

The cost from one cell to its adjacent cells (up, down, left, right cell) is 1.

Input

Here you are given two values n, m and a grid of n*m size(1<=n, m<=100) where (0<=grid[i][j]<=2)

There will be  at least one contestant in the given grid.

Output

Print the total minimum travel cost if possible to arrange a contest otherwise -1.

Sample

InputOutput
3 5
0 0 1 0 0
0 0 0 0 0
1 0 2 0 1
7

If you arrange a contest of (1,2) position then from (0,2) cost is 1,from (2,0) cost is 3 and from (2,4) cost is 3.
So total cost will be 1+3+3=7 and that’s the minimum total travel cost.


Submit

Login to submit.

Statistics

100% Solution Ratio
Guess.WhoEarliest, 1M ago
Cloud_Fastest, 0.0s
RobbinLightest, 5.7 MB
RobbinShortest, 1365B
Toph uses cookies. By continuing you agree to our Cookie Policy.