Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- /*
- Problem 1:
- The demons had captured the princess (P) and imprisoned her in the bottom-right corner of a dungeon.
- The dungeon consists of M x N rooms laid out in a 2D grid. Our valiant knight (K) was initially positioned
- in the top-left room and must fight his way through the dungeon to rescue the princess.
- The knight has an initial health point represented by a positive integer. If at any point his health point
- drops to 0 or below, he dies immediately.
- Some of the rooms are guarded by demons, so the knight loses health (negative integers) upon entering these
- rooms; other rooms are either empty (0’s) or contain magic orbs that increase the knight’s health (positive integers).
- In order to reach the princess as quickly as possible, the knight decides to move only rightward or downward in each step.
- Write a function to determine the knight’s minimum initial health so that he is able to rescue the princess.
- For example, given the dungeon below, the initial health of the knight must be at least 7 if he follows the optimal path
- RIGHT-> RIGHT -> DOWN -> DOWN.
- -2(K) -3 3
- -5 -10 1
- 10 30 -5(P)
- */
- #include <bits/stdc++.h>
- #define inp(x) scanf("%d",&x)
- #define loop(i,n) for(int i=0;i<n;++i)
- #define rloop(i,n) for(int i=n-1;i>=0;--i)
- #define pb push_back
- #define mp make_pair
- #define ll long long
- using namespace std;
- //-------------------------------------------------//
- int m, n;
- int getMinHP(vector<vector<int>> a, vector<vector<int>> &c, int i, int j){
- if(c[i][j] != -1)
- return c[i][j];
- if(i == m-1)
- return c[i][j] = max(0, getMinHP(a, c, i, j+1) - a[i][j]);
- if(j == n-1)
- return c[i][j] = max(0, getMinHP(a, c, i+1, j) - a[i][j]);
- return c[i][j] = min(
- max(0, getMinHP(a, c, i, j+1) - a[i][j]),
- max(0, getMinHP(a, c, i+1, j) - a[i][j])
- );
- }
- int main(){
- cin >> m >> n;
- vector<vector<int>> a(m, vector<int> (n, 0));
- vector<vector<int>> c(m, vector<int> (n, -1));
- for(int i = 0; i < m; ++i)
- for(int j = 0; j < n; ++j)
- cin >> a[i][j];
- c[m-1][n-1] = max(0, 1 - a[m-1][n-1]);
- cout << getMinHP(a, c, 0, 0) << endl;
- //Debug
- // for(int i = 0; i < m; ++i,cout << endl)
- // for(int j = 0; j < n; ++j)
- // cout << c[i][j] << " ";
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement