BFS | Solution for LeetCode#2577
\n\n# Intuition\n Describe your first thoughts on how to solve this problem. \nThe problem requires finding the minimum time to reach the bottom-right cell of a
![image.png](https://assets.leetcode.com/users/images/b53f0a99-e29c-4abb-9716-563c03547c76_1732851323.9855087.png)\n\n# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nThe problem requires finding the minimum time to reach the bottom-right cell of a grid, where each cell contains a time value. The intuition is to use a priority queue (min-heap) to always process the cell with the minimum time first, similar to Dijkstra\'s algorithm.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n1. Use a priority queue to store cells to visit, ordered by time.\n2. Start from the top-left cell (0,0) with time 0.\n3. For each cell, check its neighbors:\n\t- If the neighbor\'s time is less than or equal to current time + 1, we can move there immediately.\n\t- If not, we need to wait. The waiting time is calculated to be the minimum even number of steps required.\n4. Keep track of visited cells to avoid revisiting.\n5. Continue until we reach the bottom-right cell or exhaust all possibilities.\n\n# Complexity\n- Time complexity: O(mn log(mn))\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: O(mn)\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```java []\nclass Solution {\n    public int minimumTime(int[][] grid) {\n        int m=grid.length;\n        int n=grid[0].length;\n        PriorityQueue<int[]> pq=new PriorityQueue<>((a,b)->a[2]-b[2]);  // Array: row, col, value\n        boolean[][] visited=new boolean[m][n];\n        \n\n        if (grid[0][1] > 1 && grid[1][0] > 1){           \n            return -1;\n        }\n\n        int[][] moves={ {0,-1},{0,1},{-1,0},{1,0}};\n\n        pq.add(new int[]{0,0,0});\n        while(!pq.isEmpty()){\n            int[] arr=pq.poll();\n            int row=arr[0];\n            int col=arr[1];\n            int time=arr[2];\n            \n            if(row==m-1 && col==n-1){\n                return time;\n            } \n\n            if(visited[row][col]) continue;\n            visited[row][col]=true;\n\n\n            for(int[] move:moves){\n                int nrow=row+move[0];\n                int ncol=col+move[1];\n\n                if(nrow>=0 && nrow<m && ncol>=0 && ncol<n && !visited[nrow][ncol]){\n                    int newtime=0; \n                    \n                    // if(time+1>=grid[nrow][ncol]) newtime=time+1;\n                    // else if((grid[nrow][ncol]-time)%2==0) newtime=grid[nrow][ncol]+1; //even\n                    // else newtime=grid[nrow][ncol]; //odd\n\n                    int diff=grid[nrow][ncol]-time;                    \n                    if(diff<=1) newtime=time+1;                \n                    else newtime=time+1+(diff/2)*2;\n\n                    pq.add(new int[]{nrow,ncol,newtime});\n                    \n                }\n            }\n\n\n        }\n\n        return -1;\n    }\n}\n```
['Java']