# [Solved] Grid Path codechef solution

## Grid Path codechef solution

There is a grid containing NN rows and NN columns. The cell at the ithith row from the top and jthjth column from the left is a passable space if Si,jSi,j is '.' and a blocked cell if Si,jSi,j is '#'.

Chef is at the top-left cell and wants to reach the bottom-right cell. Chef can move one cell down, or right to a passable cell. He can’t leave the grid. If Chef is at the cell (i,j)(i,j), he can collect Ai,jAi,j coins.

Now, Chef has a special ability using which he can make all the blocked cells in a path of length KK into passable cells. Chef uses this ability before moving from the top-left cell. It is possible that some of the cells in the chosen KK length path are already passable. More formally, Chef can choose a sequence of KK cells such that for each ii (1i<K)(1≤i<K), the ithith and (i+1)th(i+1)th cells of the sequence are adjacent and make all these KK cells passable.

Find the maximum amount of coins Chef can collect in the path from the top-left cell to the bottom-right cell. Print 1−1 if it is impossible to reach the bottom-right cell.

Note: Two cells are considered to be adjacent if they share a common side. The cell (i,j)(i,j) has four adjacent cells i.e. the cells (i1,j)(i−1,j)(i+1,j)(i+1,j)(i,j1)(i,j−1) and (i,j+1)(i,j+1). It is guaranteed that the top-left cell of the grid is a passable cell.

### Input Format

The first line of the input contains a single integer TT denoting the number of test cases. The description of TT test cases follows.

• The first line of each test case contains two space-separated integers N,KN,K.
• NN lines follow. The ithith of these lines contains a string SiSi of length NN. The jthjth character of SiSi is '.' if the cell (i,j)(i,j) is passable, or '#' if it is a blocked cell.
• Next NN lines follow. The ithith of these lines contains NN space-separated integers Ai,jAi,j, denoting the number of coins in the cell (i,j)(i,j).

### Output Format

For each test case, print a single line containing one integer – the maximum amount of coin Chef can collect in the path or 1−1 if it is impossible to reach the bottom-right cell.

### Constraints

• 1T41031≤T≤4⋅103
• 2N1502≤N≤150
• 0K2N20≤K≤2⋅N−2
• 1Ai,j1051≤Ai,j≤105
• Si,jSi,j is either '.' or '#'.
• It is guaranteed that the top-left cell of the grid is a passable cell.
• Sum N2N2 over all testcases does not exceed 31053⋅105.

### Sample Input 1

3
2 1
.#
#.
1 2
3 4
3 3
.#.
#.#
..#
1 1 1
1 1 1
1 1 1
5 4
.....
#####
.....
#####
.....
2 3 4 1 5
1 7 15 12 2
2 5 10 8 3
9 9 9 9 9
1 2 3 4 5


### Sample Output 1

8
-1
62


### Explanation

Test case 11: Chef breaks the blocked cell (2,1)(2,1) and choose the path – (1,1)(2,1)(2,2)(1,1)→(2,1)→(2,2). Total coins collected in the path is 1+3+4=81+3+4=8.

Test case 22: There is no way to choose a path of length 33 such that after breaking the blocked cells in the path, it is possible to reach the bottom-right cell.

Test case 33: Chef chooses the path of consisting of cells (2,3),(2,3), (2,4)(2,4)(3,4)(3,4)(4,4)(4,4) and break the blocked cells in this path. Then Chef chooses the path – (1,1)(1,2)(1,3)(2,3)(2,4)(3,4)(4,4)(5,4)(1,1)→(1,2)→(1,3)→(2,3)→(2,4)→(3,4)→(4,4)→(5,4) (5,5)→(5,5). Total coins collected in the path is 2+3+42+3+4 +15+12+8+15+12+8 +9+4+5=62+9+4+5=62.

## C++

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const ll N = 155, oo = 1e18;
ll dp[N][N][2*N], blocked[N][N], c[N][N];
void solve() {
int n, k; cin >> n >> k;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
char c; cin >> c;
blocked[i][j] = c == ‘#’;
}
}
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
cin >> c[i][j];
}
}
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
for (int x = 0; x <= k; ++x) {
dp[i][j][x] = -oo;
}
}
}
dp[0][0][0] = c[0][0];
auto maxi = [&](ll & x, ll y) -> void {
if (x < y) {
x = y;
}
};
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
if (!blocked[i][j]) {
for (int v : {0, k}) {
if (i > 0) maxi(dp[i][j][v], dp[i – 1][j][v] + c[i][j]);
if (j > 0) maxi(dp[i][j][v], dp[i][j – 1][v] + c[i][j]);
}
}
for (int s = 1; s <= k; ++s) {
if (i > 0) maxi(dp[i][j][s], dp[i – 1][j][s – 1] + c[i][j]);
if (j > 0) maxi(dp[i][j][s], dp[i][j – 1][s – 1] + c[i][j]);
}
}
}
ll ans = -oo;
for (int i = 0; i <= k; ++i) {
maxi(ans, dp[n – 1][n – 1][i]);
}
ans = max(ans, -1LL);
cout << ans << ‘\n’;
}
int main() {
ios::sync_with_stdio(0); cin.tie(0);
int T = 1; cin >> T;
for (int tc = 1; tc <= T; ++tc) {
solve();
}
}

Also read : Bus full of passengers solution codechef

Also read : Friend Groups In A Line solution codechef