# Minimum Time to Visit a Cell In a Grid

unknown
c_cpp
15 days ago
2.6 kB
6
Indexable
Never
```/*Intuition
Just Simple Dijkstra’s implementation we try to go to all nodes possible from current code and if we can't reach there at given time than we assume that travel back and forth and increase time, and if value of new time for that node is less than the current value in resultant vector than update and add that in priority queue.

Complexity
Time complexity:
O( E log(V) ) { for Dijkstra’s Algorithm }

Space complexity:
O( |E| + |V| ) { for priority queue and dist array } + O( |V| ) { for storing the final path }

Where E = Number of edges and V = Number of Nodes.

Code
*/

class Solution {
public:
int minimumTime(vector<vector<int>>& grid)
{
int n = grid.size();
int m = grid[0].size();
vector<vector<int>> res(n,vector<int>(m,1e9));

if(grid[0][0] != 0) retrun -1;

if(grid[0][1]>grid[0][0]+1 && grid[1][0]>grid[0][0]+1)
{
return -1;
}

priority_queue<pair<int,pair<int,int>>,vector<pair<int,pair<int,int>>>,greater<pair<int,pair<int,int>>>> pq;

pq.push({0,{0,0}});

int nr[] = {-1,0,1,0};
int nc[] = {0,1,0,-1};

while(!pq.empty())
{
auto it = pq.top();
pq.pop();
int time = it.first;
int r = it.second.first;
int c = it.second.second;

for(int i=0;i<4;i++)
{
int x = r + nr[i];
int y = c + nc[i];

if(x>=0 && x<n && y>=0 && y<m)
{
int ntime;

if(time + 1 < grid[x][y])
{
ntime = grid[x][y];

if(((time+1)+ntime)%2)
{
ntime++;
}
}

else
{
ntime = time+1;
}

// We will go back and forth with prev. node till time will be
// greater or equal
if(ntime < res[x][y])
{
res[x][y]=ntime;
pq.push({ntime,{x,y}});
}
}
}
}

if(res[n-1][m-1]==INT_MAX)
{
res[n-1][m-1]=-1;
}
return res[n-1][m-1];
}
};```