Defuse the bombs!
All submissions for this problem are available.
Sherlock and Watson, tired of solving mysteries all day, take the subways of London to get back to Baker Street. Just to ruin their free time, Moriarty has rigged the entire subway with highly powerful bombs. The bombs are planted both on the tracks as well as the stations. It is up to Sherlock and Watson to save the city, again.
Sherlock knows the complete map of London’s subway system – which can be simply drawn as a 2D grid where each cell represents a region in London. Using “his eyes and ears all over the city” – the Homeless Network, Sherlock has found the places where the bombs are planted and the type of bombs planted. In order to maximize the efficiency of defusing the bombs, Sherlock and Watson plan on starting at 2 different corners of the map. Watson suggested that they should start at the diagonally opposite corners of the map. However Sherlock felt that it is too mainstream and wants to start at two adjacent corners of the map – Sherlock from the top-left corner and Watson from the bottom-left corner.
Once they’ve started, Sherlock can move to the cell to the right of his current cell or to the cell below. Similarly, Watson can move to the cell to his right or the cell above. Ultimately, through a sequence of bomb defusal, they will end up in a cell that is diagonally opposite to their start cell, i.e. Sherlock should reach the bottom-right corner and Watson should reach the top-right corner. Clearly, Sherlock and Watson have to cross each other’s paths before reaching their destination cells. The bombs can be defused only once in such cases.
Every cell in the map can be in one of the following 3 states –
i. The region is blocked. It is denoted by -1 on the map.
ii. The region is a track rigged with a bomb.
iii. The region is a station rigged with a bomb.
Obviously, Sherlock and Watson cannot traverse through the blocked regions. Since they are experts in defusing a bomb, they can do it zero units of time. Every non-blocked region has an associated cost – the cost to defuse the bomb in that cell. For any cell they visit, they will always defuse the bomb in that cell. Their main objective is to minimize the total cost of defusing the bombs. However, being the good guys, they do not want the people at the stations to lose their lives, so they have to defuse the bombs at all the stations.
Can you help him calculate the minimum cost that they have to spend, without leaving any station to explode?
The first line of the input has a single integer T, denoting the number of test cases. Each test case begins with 2 integers N and M denoting the number of rows and columns in the map. N lines follow, each having M values that can be an integer, denoting the cost of defusing the bomb in that region or -1 if the region is blocked.
In the next line an integer K is given, denoting the number of stations in London’s subway. The next K lines have 2 integers X and Y, meaning that the cell at row X (1 indexed) and column Y (1 indexed) in the grid is a station
For each test case, print a single integer denoting the minimum cost that has to be spent, without leaving any station to explode. If there isn’t any route in which the bombs are defused at all the stations or if Sherlock and Watson can’t reach their corresponding destinations, print -1.
1 <= T <= 10
3 <= N,M <= 1000
-1 <= grid[i][j] <= 1000
1 <= K <= 100
1 <= X <= N
1 <= Y <= M
Sample Test Case:
1 2 3
4 -1 6
7 8 9
|Time Limit:||1 - 4 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.5, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.