Solution using Dijkstra Algorithm in C++
Intuition\nThe intuition behind this approach is to maximize health at every step to ensure survival while reaching the destination. The key ideas are:\n\n- Max
# Intuition\nThe intuition behind this approach is to maximize health at every step to ensure survival while reaching the destination. The key ideas are:\n\n- Maximizing Health: Instead of minimizing cost, the goal is to maximize the remaining health at each cell. This increases the chance of survival through unsafe cells.\n\n- Priority Queue (Max-Heap): By using a max-heap, the algorithm prioritizes exploring paths that leave you with the most health, ensuring you explore the most promising paths first.\n\n- Greedy Approach: The algorithm makes locally optimal choices (choosing the highest health path) to increase the chances of a globally optimal result (reaching the goal with positive health).\n\n- Avoid Redundant Work: The maxHealth array ensures that the algorithm only explores new paths that offer more health, avoiding unnecessary or inefficient paths.\n\n# Approach\nThe approach uses a modified Dijkstra\'s algorithm to maximize health while traversing the grid. Here\'s the concise explanation:\n\n - Max-Heap (Priority Queue): You prioritize paths that leave the player with the most health by using a max-heap. This ensures you explore the most promising paths first.\n\n- Health Tracking (maxHealth): A 2D array maxHealth tracks the highest health you can have when reaching each cell. If a new path gives more health, update it and explore further.\n\n- Neighbor Exploration: From each cell, you check the four neighbors (up, down, left, right) and calculate the remaining health. Only push the neighbor into the queue if it results in more health than previously seen.\n\n- Goal: The algorithm terminates successfully if you reach the bottom-right corner with at least 1 health. If no valid path is found, it returns false.\n\n# Complexity\n- Time complexity: O((n*m)*log(n*m))\n\n- Space complexity: O(n*m)\n\n# Code\n```cpp []\nclass Solution {\npublic:\n    bool findSafeWalk(vector<vector<int>>& grid, int health) {\n        int n = grid.size(), m = grid[0].size();\n        vector<vector<int>> maxHealth(n, vector<int> (m, INT_MIN));\n        priority_queue<pair<int,pair<int,int>>> pq;\n        pq.push({health-grid[0][0], {0,0}});\n        maxHealth[0][0] = health - grid[0][0];\n        int dx[4] = {-1,0,1,0};\n        int dy[4] = {0,1,0,-1};\n        while(!pq.empty()){\n            int currHealth = pq.top().first;\n            int r = pq.top().second.first;\n            int c = pq.top().second.second;\n            pq.pop();\n            if(r == n-1 && c == m-1 && currHealth >= 1) return true;\n            for(int i = 0; i < 4; i++){\n                int nr = r + dx[i];\n                int nc = c + dy[i];\n                if(nr >= 0 && nr < n && nc >= 0 && nc < m){\n                    if(maxHealth[nr][nc] < currHealth - grid[nr][nc]){\n                        maxHealth[nr][nc] = currHealth - grid[nr][nc];\n                        pq.push({currHealth-grid[nr][nc], {nr,nc}});\n                    }\n                }\n            }\n        }\n        return false;\n    }\n};\n```
['Breadth-First Search', 'Heap (Priority Queue)', 'Matrix', 'Shortest Path', 'C++']