There is a modern city where people send their children to train under a master of programming. But this year, the master has received so many applicants that he decides to screen them using a simple test. His test comprises of traversing a grid and collecting maxium jewels. But there are certain burglars in the way. If the student gets too close to the burglar, they'll rob him off some of his treasure. And if the student moves to the block containing the burglar, he'll be immediately killed, and thus wont be able to complete his task. The burglars have a specific quota alloted to them, and they just rob the person off that much treasure. They leave the rest of the student's treasure untouched. Thus, if a student comes in an adjacent grid to one of the burglars, he'll be poorer by x jewels, where x is the alloted quota for that particular burglar. But if a cell is adjacent to two or more burglars, each of them will rob him off, taking 'sum of all burglars quota' number of jewels. Also, if a student does not have enough jewels, his jewel tally will go into negative.
The task of the student is to go from the start location to the master's location, gathering as many jewels as possible. If the number of jewels collected by the student is the maximum possible for that particular grid and burglar setting, then the master accepts the child as his student.
Your task is to help the student clear this test, given the grid, number of jewels at each cell, and the burglar position. The output will be the maximum number of jewels collected.
The student starts at the top left position of the grid and moves to the master's location, at the bottom right. The constraint is that the student can only move downwards or towards the right, one cell at a time, and cannot skip cells.
1. The neighbourhood of the burglar is defined as all the cells surrounding him. This will be the 8 cells surrounding him, unless he is on one of the edges, when it will be less than 8.
Also, if the student moves from a cell in the neighbourhood of the burglar to another cell in his neighbourhood, the burglar will rob him twice. That is, for every cell that he steps which is in control of the burglar, he'll have to part with his jewels.
2. It might so happen that a cell in the neighbourhood of the burglar might contain a lot of jewels, and the burglar might just rob some. For eg. If the cell adjacent to the burglar has 100jewels and the burglar just robs 10, the student will be richer by 90jewels by moving into that cell. In such cases, it might be profitable to move into such cells.
The first line of input is m,n where m is the number of rows and n is the number of columns in the grid.
The next m rows have n comma seperated values, where each number can be either a positive integer, negative integer or 0. A positive integer represents the number of jewels present at that particular cell. 0 means that no jewel will be found at that cell. A negative value indicates that there is a burglar at that location, with the negative value as his robbing quota.
The starting location is the 1*1 cell and the ending is m*n cell, both of which have the value 0.
The output will be the maximum number of jewels that can be collected.
The following example on the 4*4 grid is shown:
Input: 4,4 0,23,20,-32 13,14,44,-44 23,19,41,9 46,27,20,0 Output: 129
|Time Limit:||1.06778 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, JAVA, PYTH, PYTH 3.6, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, 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