Beats 100% ✅ ✅ | Dijkstra's | Heap 🌟 🌟
Intuition\nThe problem resembles a shortest path problem where we need to reach the bottom-right corner of a grid with the minimum time cost. Since each cell ha
### Intuition\nThe problem resembles a shortest path problem where we need to reach the bottom-right corner of a grid with the minimum time cost. Since each cell has a specific time to traverse, and there\'s a toggle condition affecting the time cost, Dijkstra\'s algorithm (minimum priority queue) is well-suited. We track the minimum time required to reach each cell with a certain state (`flag`), representing a two-state toggle.\n\n### Approach\n1. **Use a Priority Queue**: Initialize a priority queue to manage states efficiently by their minimum cumulative distance. Each entry in the queue will track `(current distance, x, y, flag)`.\n2. **Direction Array**: Define movement directions (right, down, left, up) to navigate the grid.\n3. **3D Visited Array**: Use a `boolean[][][]` array to record visited cells with two possible `flag` states, preventing redundant processing.\n4. **Dijkstra\u2019s Logic**:\n   - Start from the top-left cell `(0, 0)` with an initial distance of `0` and `flag = true`.\n   - At each cell, calculate the next possible distance based on the `flag` state:\n     - If `flag` is `true`, add 1 to the distance and toggle `flag` to `false` for the next cell.\n     - If `flag` is `false`, add 2 to the distance and toggle `flag` to `true` for the next cell.\n   - Push these states to the priority queue, always prioritizing the least cumulative distance.\n   - If the bottom-right cell is reached, return the distance.\n\n### Complexity\n- **Time Complexity**:  \n  Since we process each cell potentially with two states (`flag = true` or `false`), the complexity is approximately \\(O(n \\times m \\times \\log(n \\times m))\\), where `n` and `m` are the grid dimensions. The logarithmic factor arises from the priority queue operations.\n\n- **Space Complexity**:  \n  The space complexity is \\(O(n \\times m)\\), considering the `visited` array and the space used by the priority queue, which holds states for each cell.\n\n# Code\n```python3 []\nclass Solution:\n    def minTimeToReach(self, moveTime: List[List[int]]) -> int:\n        n,m = len(moveTime),len(moveTime[0])\n        vis = [[False for i in range(m)] for j in range(n)]\n        dir = [(0,1),(1,0),(-1,0),(0,-1)]\n        pq = [(0,0,0,True)]\n        while pq:\n            dist,i,j,flag = heapq.heappop(pq)\n            if i==n-1 and j==m-1:\n                return dist\n            for dx,dy in dir:\n                x,y = i+dx,j+dy\n                if 0<=x<n and 0<=y<m and not vis[x][y]:\n                    vis[x][y] = True\n                    if flag:\n                        newDist = max(dist+1,moveTime[x][y]+1)\n                    else:\n                        newDist = max(dist+2,moveTime[x][y]+2)\n                    heapq.heappush(pq,(newDist,x,y,not flag))\n        return -1\n```\n```java []\nclass Tuple {\n    int dist;\n    int x;\n    int y;\n    boolean flag;\n    Tuple(int dist,int x,int y,boolean flag){\n        this.dist = dist;\n        this.x = x;\n        this.y = y;\n        this.flag = flag;\n    }\n}\nclass Solution {\n    public int minTimeToReach(int[][] moveTime) {\n        int n = moveTime.length;\n        int m = moveTime[0].length;\n        PriorityQueue<Tuple> pq = new PriorityQueue<>((a,b)->a.dist-b.dist);\n        boolean[][] vis = new boolean[n][m];\n        int[][] dir = {{0,1},{1,0},{-1,0},{0,-1}};\n        pq.add(new Tuple(0,0,0,true));\n        while(!pq.isEmpty()){\n            Tuple t = pq.poll();\n            int dist = t.dist;\n            int i = t.x;\n            int j = t.y;\n            boolean flag = t.flag;\n            if(i==n-1 && j==m-1) {\n                return dist;\n            }\n            for (int[] d : dir) {\n                int dx = d[0];\n                int dy = d[1];\n                int x = i+dx;\n                int y = j+dy;\n                int newDist;\n                if(0<=x && x<n && 0<=y && y<m && !vis[x][y]) {\n                    vis[x][y] = true;\n                    if(flag) {\n                        newDist = Math.max(moveTime[x][y]+1,dist+1);\n                        pq.add(new Tuple(newDist,x,y,false));\n                    }\n                    else {\n                        newDist = Math.max(moveTime[x][y]+2,dist+2);\n                        pq.add(new Tuple(newDist,x,y,true));\n                    }\n                }\n            }\n        }\n        return -1;\n    }\n}\n```
['Heap (Priority Queue)', 'Shortest Path', 'Java', 'Python3']