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.
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.
Print the total minimum travel cost if possible to arrange a contest otherwise -1.
Input | Output |
---|---|
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. |