<p>You are given an <code>n x n</code> integer matrix <code>grid</code> where each value <code>grid[i][j]</code> represents the elevation at that point <code>(i, j)</code>.</p>

<p>The rain starts to fall. At time <code>t</code>, the depth of the water everywhere is <code>t</code>. You can swim from a square to another 4-directionally adjacent square if and only if the elevation of both squares individually are at most <code>t</code>. You can swim infinite distances in zero time. Of course, you must stay within the boundaries of the grid during your swim.</p>

<p>Return <em>the least time until you can reach the bottom right square </em><code>(n - 1, n - 1)</code><em> if you start at the top left square </em><code>(0, 0)</code>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2021/06/29/swim1-grid.jpg" style="width: 164px; height: 165px;" />
<pre>
<strong>Input:</strong> grid = [[0,2],[1,3]]
<strong>Output:</strong> 3
Explanation:
At time 0, you are in grid location (0, 0).
You cannot go anywhere else because 4-directionally adjacent neighbors have a higher elevation than t = 0.
You cannot reach point (1, 1) until time 3.
When the depth of water is 3, we can swim anywhere inside the grid.
</pre>

<p><strong class="example">Example 2:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2021/06/29/swim2-grid-1.jpg" style="width: 404px; height: 405px;" />
<pre>
<strong>Input:</strong> grid = [[0,1,2,3,4],[24,23,22,21,5],[12,13,14,15,16],[11,17,18,19,20],[10,9,8,7,6]]
<strong>Output:</strong> 16
<strong>Explanation:</strong> The final route is shown.
We need to wait until time 16 so that (0, 0) and (4, 4) are connected.
</pre>

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

<ul>
	<li><code>n == grid.length</code></li>
	<li><code>n == grid[i].length</code></li>
	<li><code>1 &lt;= n &lt;= 50</code></li>
	<li><code>0 &lt;= grid[i][j] &lt;&nbsp;n<sup>2</sup></code></li>
	<li>Each value <code>grid[i][j]</code> is <strong>unique</strong>.</li>
</ul>

class Solution {

public:

    struct edgeData
    {
        int cost;
        int x;
        int y;

        bool operator<(const edgeData &data) const
        {
            return cost<data.cost;
        }
    };

    struct vertexData
    {
        int cost;
        int x;
        int y;
        bool visited;
        int value;

        vector<edgeData> neighborList;

        bool operator<(const vertexData &data) const
        {
            return cost<data.cost;
        }
    };

    void printGraph(const map<pair<int,int>, vertexData> &vertices, const int &t)
    {
        cout<<"T "<<t<<endl;
        for(auto iter = vertices.begin(); iter!=vertices.end(); iter++)
        {
            const vertexData &currVertex = iter->second;
            cout<<"["<<currVertex.x<<" "<<currVertex.y<<"] : ";
            for(int k=0;k<currVertex.neighborList.size();k++)
            {
                cout<<"["<<currVertex.neighborList[k].x<<" "<<currVertex.neighborList[k].y<<" - "<<currVertex.neighborList[k].cost<<"], ";
            }
            cout<<endl;
        }
        cout<<endl<<endl;
    }

    void setupGraph(const vector<vector<int>>& grid, map<pair<int,int>, vertexData> &vertices, const int &t, const int &width, const int &height)
    {
        for(int y=0; y<height;y++)
        {
            for(int x=0; x<width; x++)
            {
                if(grid[y][x]<=t)
                {
                    vertexData v;
                    v.x = x;
                    v.y = y;
                    v.cost = INT_MAX;
                    v.visited = false;
                    v.value = grid[y][x];
                    v.neighborList.reserve(4);


                    if(x-1>=0 && grid[y][x-1]<=t)
                    {
                        edgeData e;
                        e.x=x-1;
                        e.y=y;
                        e.cost = max(0, grid[y][x-1] - grid[y][x]);
                        v.neighborList.push_back(e);
                    }

                    if(y-1>=0 && grid[y-1][x]<=t)
                    {
                        edgeData e;
                        e.x=x;
                        e.y=y-1;
                        e.cost = max(0, grid[y-1][x] - grid[y][x]);
                        v.neighborList.push_back(e);
                    }

                    if(x+1<width && grid[y][x+1]<=t)
                    {
                        edgeData e;
                        e.x=x+1;
                        e.y=y;
                        e.cost = max(0, grid[y][x+1] - grid[y][x]);
                        v.neighborList.push_back(e);
                    }

                    if(y+1<height && grid[y+1][x]<=t)
                    {
                        edgeData e;
                        e.x=x;
                        e.y=y+1;
                        e.cost = max(0, grid[y+1][x] - grid[y][x]);
                        v.neighborList.push_back(e);
                    }
                    vertices[make_pair(x,y)] = v;
                }
            }
        }
    }

    int swimInWater(vector<vector<int>>& grid) {

        int height = grid.size();
        if(height==0)
            return 0;
        int width =grid[0].size();

        //int maxVal=INT_MIN;
        //for(int y=height-1; y>=0;y--)
        //{
        //    for(int x=width-1; x>=0; x--)
        //    {
        //        maxVal=max(maxVal, grid[y][x]);
        //    }
        //}

        int maxVal = INT_MAX;
        //start using value from first grid
        //for(int i=grid[0][0]; i<=maxVal; i++)
        //for(int i=maxVal; i<=maxVal; i++)
        int i=maxVal;
        {
            //set anything below i to zero and solve djistra algorithm
            map<pair<int,int>, vertexData> vertices;

            //setup graph
            setupGraph(grid, vertices, i, width, height);            

            //print vertices
            //printGraph(vertices, i);
                        
            multiset<edgeData> list;

            int costSoFar=0;
            //start node
            {  
                vertexData &currData=vertices[make_pair(0,0)];          
                currData.cost = grid[0][0];
                list.insert({currData.cost, currData.x, currData.y});
                costSoFar = currData.cost;
            }

            
            while(!list.empty())
            {
                edgeData data = *list.begin();
                
                costSoFar = max(data.cost, costSoFar);
                //cout<<"I "<<i<<" P ["<<data.x<<" "<<data.y<<"] C "<<data.cost<<" "<<costSoFar<<endl;

                               
                //destination reached
                if(data.x==width-1 && data.y==height-1)
                {
                    maxVal=data.cost;
                    break;
                    //return maxVal;
                }
                    //return i;

                //erase from the list
                list.erase(list.begin());                
                vertexData &currData=vertices[make_pair(data.x,data.y)];

                if(currData.visited)
                    continue;
                currData.visited = true;
                //cout<<"P ["<<currData.x<<" "<<currData.y<<"] S "<<currData.neighborList.size()<<endl;

                for(int j=0;j<currData.neighborList.size(); j++)
                {
                    //cout<<"C ["<<currData.neighborList[j].x<<" "<<currData.neighborList[j].y<<"] ";
                    vertexData &nextData=vertices[make_pair(currData.neighborList[j].x,currData.neighborList[j].y)];
                    
                    if(!nextData.visited)
                    {
                        //int newCost = data.cost + currData.neighborList[j].cost;
                        int newCost = data.cost + max(0, nextData.value - costSoFar) ;
                        //cout<<"P ["<<nextData.x<<" "<<nextData.y<<"] C "<<nextData.cost<<" > "<<newCost<<" ";
                        if(nextData.cost>newCost)
                        {
                            nextData.cost = newCost;                        
                            list.insert({nextData.cost, currData.neighborList[j].x, currData.neighborList[j].y});
                            //cout<<"A ["<<nextData.x<<" "<<nextData.y<<"] C "<<nextData.cost; 
                        }
                        //else 
                        //    break;
                                              
                    }
                    //cout<<endl;;
                }  
                //cout<<endl;              
            }
        }
        return maxVal;
    }
};
22773