| 10 | using namespace std; |
| 11 | |
| 12 | int f(int i, int j1, int j2, vector<vector<int>> &grid, int n, int m, vector<vector<vector<int>>> &dp) |
| 13 | { |
| 14 | if (i == n) |
| 15 | { |
| 16 | return 0; |
| 17 | } |
| 18 | if (dp[i][j1][j2] != -1) |
| 19 | { |
| 20 | return dp[i][j1][j2]; |
| 21 | } |
| 22 | int mx = INT_MIN; |
| 23 | // if Alice can move to the left column in the row below |
| 24 | if (((j1 - 1) >= 0)) |
| 25 | { |
| 26 | // if Bob can move to the same column in the row below |
| 27 | mx = max(mx, f(i + 1, j1 - 1, j2, grid, n, m, dp)); |
| 28 | // if Bob can move to the left column in the row below |
| 29 | if ((j2 - 1) >= 0) |
| 30 | { |
| 31 | mx = max(mx, f(i + 1, j1 - 1, j2 - 1, grid, n, m, dp)); |
| 32 | } |
| 33 | // if Bob can move to the right column in the row below |
| 34 | if ((j2 + 1) < m) |
| 35 | { |
| 36 | mx = max(mx, f(i + 1, j1 - 1, j2 + 1, grid, n, m, dp)); |
| 37 | } |
| 38 | } |
| 39 | // if Alice can move to the same column in the row below |
| 40 | // if Bob can move to the same column in the row below |
| 41 | mx = max(mx, f(i + 1, j1, j2, grid, n, m, dp)); |
| 42 | // if Bob can move to the left column in the row below |
| 43 | if ((j2 - 1) >= 0) |
| 44 | { |
| 45 | mx = max(mx, f(i + 1, j1, j2 - 1, grid, n, m, dp)); |
| 46 | } |
| 47 | // if Bob can move to the right column in the row below |
| 48 | if ((j2 + 1) < m) |
| 49 | { |
| 50 | mx = max(mx, f(i + 1, j1, j2 + 1, grid, n, m, dp)); |
| 51 | } |
| 52 | // if Alice can move to the right column in the row below |
| 53 | if (((j1 + 1) < m)) |
| 54 | { |
| 55 | // if Bob can move to the same column in the row below |
| 56 | mx = max(mx, f(i + 1, j1 + 1, j2, grid, n, m, dp)); |
| 57 | // if Bob can move to the left column in the row below |
| 58 | if ((j2 - 1) >= 0) |
| 59 | { |
| 60 | mx = max(mx, f(i + 1, j1 + 1, j2 - 1, grid, n, m, dp)); |
| 61 | } |
| 62 | // if Bob can move to the right column in the row below |
| 63 | if ((j2 + 1) < m) |
| 64 | { |
| 65 | mx = max(mx, f(i + 1, j1 + 1, j2 + 1, grid, n, m, dp)); |
| 66 | } |
| 67 | } |
| 68 | if (j1 == j2) |
| 69 | { |
no test coverage detected