Dijkstra’s algorithm with Explanation
Intuition\n\nThe goal of the problem is to determine whether it\'s possible to reach the bottom-right cell of a grid, starting from the top-left cell, while mai
# Intuition\n\nThe goal of the problem is to determine whether it\'s possible to reach the bottom-right cell of a grid, starting from the top-left cell, while maintaining at least 1 health point. The cells in the grid can either contribute to reducing your health (indicated by a positive integer) or can be free (indicated by 0). You can only move up, down, left, or right.\n\n# Approach\nTo solve this problem, we can use a modified Dijkstra\u2019s algorithm with a priority queue (max-heap). Here\'s the step-by-step approach:\n\n**Initialize Variables:**\nRead the dimensions of the grid.\nDefine possible movement directions (up, down, left, right).\nCreate a priority queue to manage the health points effectively.\nCreate a cost matrix to track the maximum health points remaining when reaching each cell.\n\n**Push Initial State:**\nStart from the top-left cell, pushing the initial health minus the health cost of that cell into the priority queue.\n\n**Process the Queue:**\nWhile the queue is not empty, pop the cell with the highest remaining health.\nFor each possible direction, calculate the new cell\'s position and check if moving to that cell with the current health results in a greater remaining health than previously recorded in the cost matrix.\nIf valid, update the cost matrix and push the new state into the queue.\nCheck End Condition:\n\nAt the end, check if the remaining health at the bottom-right cell is greater than or equal to 1.\n\n# Complexity\n- **Time complexity:**\nO(m\u22C5n\u22C5log(m\u22C5n)) where m is the number of rows and n is the number of columns in the grid. Each cell can potentially be added to the priority queue once, and maintaining the priority queue takes logarithmic time relative to its size.\n\n\n- **Space complexity:**\nO(m\u22C5n) for storing the cost matrix and the priority queue.\n\n# Code\n```cpp []\n// Using p as a shorthand for pair<int, int>\nusing p = pair<int,int>;\n\nclass Solution {\npublic:\n    // Function to determine if a safe walk to the bottom-right cell is possible\n    bool findSafeWalk(vector<vector<int>>& grid, int health) {\n        // Get the number of rows (m) and columns (n) in the grid\n        int m = grid.size(), n = grid[0].size();\n        \n        // Define the possible movement directions (right, down, left, up)\n        vector<p> directions = {{0,1},{1,0},{0,-1},{-1,0}};\n        \n        // Max-Heap priority queue to store the remaining health and current cell position\n        priority_queue<pair<int,p>> pq;\n        \n        // Push the initial state (remaining health after starting at the top-left cell)\n        pq.push({health - grid[0][0], {0, 0}});\n        \n        // 2D vector to track the maximum health remaining at each cell\n        vector<vector<int>> cost(m, vector<int>(n, INT_MIN));\n        \n        // Initialize the starting cell\'s health after stepping on it\n        cost[0][0] = health - grid[0][0];\n        \n        // While there are positions to explore in the priority queue\n        while(!pq.empty()){\n            // Get the current remaining health and position from the top of the queue\n            auto current_health = pq.top().first;\n            auto [row, col] = pq.top().second;\n            pq.pop(); // Remove this position from the queue\n            \n            // Explore each possible direction from the current position\n            for(auto it: directions){\n                // Calculate the new cell position\n                int i = row + it.first;\n                int j = col + it.second;\n                \n                // Check if the new position is within bounds and has better health\n                // Remaining health must be greater than the health cost of the new cell\n                if(i < m && i >= 0 && j < n && j >= 0 \n                   && current_health - grid[i][j] > cost[i][j] \n                   && current_health - grid[i][j] > 0) {\n                    // Update the maximum health at the new position\n                    cost[i][j] = current_health - grid[i][j];\n                    \n                    // Push the new state into the priority queue\n                    pq.push({cost[i][j], {i, j}});\n                }\n            }\n        }\n        \n        // Check if the bottom-right cell can be reached with at least 1 health point\n        return (cost[m-1][n-1] >= 1) ? true : false;\n    }\n};\n\n```\n**Explanation with Test Case**\nLet\'s analyze the provided test case:\n\n**Input:**\n```\ngrid = [[0,1,0,0,0],[0,1,0,1,0],[0,0,0,1,0]]\nhealth = 1\n```\n\n**Initialization:**\nStarting health = 1.\nStart from (0,0) which has 0 health cost. Remaining health after stepping in cell (0,0) is 1 - 0 = 1.\n\n**Processing the Queue:**\nFrom (0,0), you can move to (0,1) and (1,0).\nMoving to (0,1) costs 1, so remaining health will be 1 - 1 = 0. However, the health should be strictly greater than 0 to continue, so this move is invalid.\nMove to (1,0) which has 0 cost. Remaining health becomes 1 - 0 = 1, which is valid. Push (1,0) into the queue.\nContinuing from (1,0):\n\nFrom (1,0), you can move to (1,1) (which costs 1), so the remaining health becomes 1 - 1 = 0, which is invalid.\nMove down to (2,0), which is valid and costs 0, resulting in remaining health of 1.\nFrom (2,0):\n\nFrom (2,0), you can move to (2,1), which costs 0, remaining health is still 1. This move is valid.\nThen to (2,2), which costs 0, remaining health stays 1.\nFinally, you can move up to (1,2) which costs 0, keeping the health above 0.\nReaching the End:\n\nFrom (2,2), you can eventually find your way to the last cell (2,4) while maintaining at least 1 health.\n\n**Final Result:**\nThe cost matrix shows that the bottom-right cell (2,4) is reachable with health greater than or equal to 1.\nThus, the output is true, confirming a safe walk exists to the bottom-right cell with at least 1 health point left.\n\n\n\n
['Graph', 'C++']