<p>The demons had captured the princess and imprisoned her in <strong>the bottom-right corner</strong> of a <code>dungeon</code>. The <code>dungeon</code> consists of <code>m x n</code> rooms laid out in a 2D grid. Our valiant knight was initially positioned in <strong>the top-left room</strong> and must fight his way through <code>dungeon</code> to rescue the princess.</p>

<p>The knight has an initial health point represented by a positive integer. If at any point his health point drops to <code>0</code> or below, he dies immediately.</p>

<p>Some of the rooms are guarded by demons (represented by negative integers), so the knight loses health upon entering these rooms; other rooms are either empty (represented as 0) or contain magic orbs that increase the knight&#39;s health (represented by positive integers).</p>

<p>To reach the princess as quickly as possible, the knight decides to move only <strong>rightward</strong> or <strong>downward</strong> in each step.</p>

<p>Return <em>the knight&#39;s minimum initial health so that he can rescue the princess</em>.</p>

<p><strong>Note</strong> that any room can contain threats or power-ups, even the first room the knight enters and the bottom-right room where the princess is imprisoned.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2021/03/13/dungeon-grid-1.jpg" style="width: 253px; height: 253px;" />
<pre>
<strong>Input:</strong> dungeon = [[-2,-3,3],[-5,-10,1],[10,30,-5]]
<strong>Output:</strong> 7
<strong>Explanation:</strong> The initial health of the knight must be at least 7 if he follows the optimal path: RIGHT-&gt; RIGHT -&gt; DOWN -&gt; DOWN.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> dungeon = [[0]]
<strong>Output:</strong> 1
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>m == dungeon.length</code></li>
	<li><code>n == dungeon[i].length</code></li>
	<li><code>1 &lt;= m, n &lt;= 200</code></li>
	<li><code>-1000 &lt;= dungeon[i][j] &lt;= 1000</code></li>
</ul>

#include<queue>
typedef pair <long long,long long> ii1;
typedef pair <long long,ii1> ii;

class Solution {
public:

    int dx[2]={0,1};
    int dy[2]={1,0};

    bool bound(int x,int y,int n,int m)
    {
        if(x<=0 || x>n || y<=0 || y>m)
        {
            return false;
        }
        return true;
    }

    bool check(long long key,long long a[][210],int n,int m)
    {
        long long d[210][210]={0};
        bool ok[210][210]={0};
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=m;j++)
            {
                d[i][j]=-999999999999;
            }
        }
        priority_queue<ii,vector<ii>,less<ii>> pq;
        pq.push(ii(key+a[1][1],ii1(1,1)));
        d[1][1]=key+a[1][1];
        ok[1][1]=true;
        while(!pq.empty())
        {
            long long dd = pq.top().first;
            long long x = pq.top().second.first;
            long long y = pq.top().second.second;
            pq.pop();
            //cout<<dd<<" "<<x<<" "<<y<<endl;
            if(dd<=0) 
            {
                return false;
            }
            if(x==n && y==m)
            {
                return true;
            }
            if(dd != d[x][y])
            {
                continue;
            }
            ok[x][y]=true;
            for(int i=0;i<2;i++)
            {
                int newx= x + dx[i];
                int newy = y + dy[i];
                if(bound(newx,newy,n,m)&& d[newx][newy] <=d[x][y] + a[newx][newy])
                {
                    d[newx][newy]=d[x][y] + a[newx][newy];
                    pq.push(ii(d[newx][newy],ii1(newx,newy)));
                }
            }
        }
        return false;
    }

    int calculateMinimumHP(vector<vector<int>>& b) {
        long long a[210][210]={0};
        for(int i=0;i<b.size();i++)
        {
            for(int j=0;j<b[i].size();j++)
            {
                a[i+1][j+1]=b[i][j];
            }
        }        
        int n=b.size(),m=b[0].size();

        long long l=1,r=4e9;
        long long ans =0;
        //check(2,a,n,m);
        while(l<=r)
        {
            long long mid = l+ (r-l)/2;
            if(check(mid,a,n,m))
            {
                r=mid-1;
                ans =mid;
                //cout<<mid<<endl;

            }
            else
            {
                l=mid+1;;
            }
        }
        return ans;
    }
};
14100