P16658 [GKS 2018 #G] Cave Escape

Mr. Raven is stuck in a cave represented by a matrix of $N$ rows and $M$ columns, where rows are numbered from $1$ to $N$ from top to bottom, and columns are numbered from $1$ to $M$ from left to right. The cell at the i-th row and the j-th column is denoted by $(i, j)$. Mr. Raven is currently at the cell $(S_R, S_C)$, and the exit of the cave is located at the cell $(T_R, T_C)$. Some cells of the cave may contain obstacles. Mr. Raven cannot step into a cell that has an obstacle. Other cells may contain traps. The first time that Mr. Raven enters a cell with a trap, he must spend a number of energy points equal to the strength of the trap. If he has fewer energy points than needed, he cannot enter the cell. Moreover, some other cells may contain potions. The first time that Mr. Raven enters a cell with a potion, he gains energy points equal to the strength of the potion. Mr. Raven initially has $E$ energy points. He can move between cells that share an edge (not just a corner). On the exit cell, Mr. Raven can choose not to exit the cave and continue to explore the cave if he wants to. Can you help him find the maximum number of energy points he can have when he exits the cave, if it is possible to do so?

The first line of the input gives the number of test cases, $T$. $T$ test cases follow. Each test case consists of one line with seven integers $N$, $M$, $E$, $S_R$, $S_C$, $T_R$ and $T_C$ as described above. The i-th of the next $N$ lines describes the i-th row of the cave. Each line consists of $M$ integers $V_{ij}$; the j-th of these represents the cell in the j-th column of the i-th row. Each $V_{ij}$ can be one of the following - $0$: represents an empty cell. - $-100000$: represents a cell with an obstacle. - an integer between $-99999$ and $-1$ (both inclusive): represents a trap with strength $-V_{ij}$. - an integer between $1$ and $99999$ (both inclusive): represents a potion with strength $V_{ij}$.

For each test case, output one line containing Case #x: y, where x is the test case number (starting from $1$) and y is the maximum energy points that Mr. Raven can have when he reaches the exit of the cave. If it is not possible for Mr. Raven to reach the exit, output $-1$.

In Sample Case #1, it is not possible for Mr. Raven to reach the exit. In Sample Case #2, there are no traps and no potions, which means Mr. Raven can reach exit and no matter what path he follows his energy will stay unchanged. ### Limits $1 \le T \le 100$. $1 \le N \le 100$. $1 \le M \le 100$. $0 \le E \le 100000$. $1 \le S_R \le N$. $1 \le S_C \le M$. $1 \le T_R \le N$. $1 \le T_C \le M$. $(S_R, S_C) \ne (T_R, T_C)$. $-100000 \le V_{ij} < 100000$, for all i, j. At most $15$ cells have $-100000 < V_{ij} < 0$. (There are at most $15$ traps.) $V_{S_R S_C} = 0$. (Mr. Raven's initial position is an empty cell.) $V_{T_R T_C} = 0$. (The cell with the exit is empty.) **Small dataset (Test set 1 - Visible)** There are no cells that have $V_{ij} > 0$. (There are no potions in the cave.) **Large dataset (Test set 2 - Hidden)** No additional constraints.