Bfs | priority queue | Dikstra | 𝑂(𝑛⋅𝑚⋅log⁡(𝑛⋅𝑚))
Intuition\nThe intuition was that we are given a source node and a destination node, so basically find a path (not shortest in this case).\n\n# Approach\nI impl
# Intuition\nThe intuition was that we are given a source node and a destination node, so basically find a path (not shortest in this case).\n\n# Approach\nI implemented dikstra theorum, but this time, i processed the cells with maximum health standing and checked if can reach the last node using the best path each time.\n\n# Complexity\n- Time complexity: \nTime Complexity\nInitialization: Initializing the variables and data structures takes \uD835\uDC42(\uD835\uDC5B\u22C5\uD835\uDC5A)\nO(n\u22C5m) time, where n is the number of rows and m is the number of columns in the grid.\n\nPriority Queue Operations: The priority queue (max-heap) operations dominate the time complexity:\n\nIn the worst case, we may insert all cells of the grid into the priority queue. This leads to at most \n\uD835\uDC42(\uD835\uDC5B\u22C5\uD835\uDC5A)O(n\u22C5m) insertions.\nEach insertion and extraction operation takes \n\uD835\uDC42(\nlog(\uD835\uDC5B\u22C5\uD835\uDC5A))\nO(log(n\u22C5m)) time due to the nature of heaps.\nExploration of Neighbors: For each cell, you check up to 8 neighbors (considering diagonal movement). This does not significantly change the overall complexity since each neighbor is checked at most once.\n\nPutting it all together, the overall time complexity can be approximated as:\n\n\uD835\uDC42(\uD835\uDC5B\u22C5\uD835\uDC5A\u22C5log\u2061(\uD835\uDC5B\u22C5\uD835\uDC5A))\nO(n\u22C5m\u22C5log(n\u22C5m))\n\n- Space complexity:\nO(n\u22C5m)\n\n# Code\n```cpp []\nclass Solution {\npublic:\n    bool findSafeWalk(vector<vector<int>>& grid, int health) {\n        int n = grid.size();\n        int m = grid[0].size();\n\n        if(health- grid[0][0] < 1 ) return false;\n        vector<vector<int>> vis(n, vector<int>(m, 0));\n        priority_queue<pair<int, pair<int, int>>>q;\n\n        vector<int> dirX = {0, 1, -1};\n        vector<int> dirY = {0, 1, -1};\n        health-= grid[0][0];\n        q.push({health, {0, 0}});\n        vis[0][0] = 1;\n\n        while(!q.empty()){\n            \n            int h = q.top().first; \n            int x =  q.top().second.first;\n            int y = q.top().second.second;\n            q.pop();\n            if (x == n - 1 && y == m - 1) {\n                return true;\n            }\n            // vis[x][y] = 1;\n            for(int i = 0; i < 3; i++){\n                for(int j = 0; j < 3; j++){\n\n                    if( abs(dirX[i]) == abs(dirY[j])) continue;\n                    int X = x + dirX[i];\n                    int Y = y + dirY[j];\n                    if(X < 0 || X>= n || Y < 0 || Y >=m || h - grid[X][Y] < 1) continue;\n\n                    if(vis[X][Y] ==0) {\n                        vis[X][Y] = 1;\n                        q.push({h-grid[X][Y], {X, Y}});\n                    }\n                }\n            }\n        }\n        return vis[n-1][m-1];\n\n    }\n};\n```
['Breadth-First Search', 'Graph', 'Shortest Path', 'C++']