Basic BFS Traversal
Intuition\n Describe your first thoughts on how to solve this problem. \nKeep performing BFS start from (0,0) on the four adjacent cells({i-1,j},{i,j+1},{i+1,j}
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nKeep performing BFS start from (0,0) on the four adjacent cells({i-1,j},{i,j+1},{i+1,j},{i,j-1}). \nIf you reach grid[n][m] and the health still is greater than equal to 1, return true else false.\n# Approach\n<!-- Describe your approach to solving the problem. -->\n\n1. Breadth-First Search (BFS):\n    - We use a BFS approach to explore all possible paths starting from the top-left corner.\n    - We keep track of the remaining health at each cell and update it based on the health cost of the cell.\n    - At each step, we check the four possible directions (up, down, left, right).\n    - If we reach the bottom-right corner (n-1, m-1) with at least 1 health point, return true.\n\n2. State Tracking:\n\n    - We use a 2D array maxH to track the maximum health at each cell that we have seen so far during the BFS traversal.\n    - If we reach a cell with a higher remaining health than before, we continue exploring from that cell.\n    \n3. Early Exit:\n    - If we reach the bottom-right corner and have at least 1 health point left, we can immediately return true.\n    \n4. Return:\n    - If after traversing all possible paths, we never reach the bottom-right corner with at least 1 health, return false.\n\n\n\n# Examples\n\ngrid = [[1, 10, 3],\n        [4, 5, 10],\n        [3, 1, 1]]\nhealth = 10\n1. n = 3 and m = 3, representing the number of rows and columns in the grid.\n2. maxH (maximum health at each cell) is initialized as a 3x3 matrix filled with -1\nmaxH = [[-1, -1, -1],[-1, -1, -1],[-1, -1, -1]]\n3. Queue is initialized with the first cell (top-left corner (0, 0)):\n    - Remaining health at (0, 0) after subtracting the health cost of grid[0][0] = 1: health - grid[0][0] = 10 - 1 = 9.\n    - The initial queue contains: q = [(9, (0, 0))].\n    maxH = [[9, -1, -1],[-1, -1, -1],[-1, -1, -1]]\n\n4. BFS Iteration 1\n    - Pop from the queue: node = 9, xval = 0, yval = 0.\nCheck four possible directions (up, down, left, right) from (0, 0):\n    - Move Right (to (0, 1)):\n        - New remaining health: node - grid[0][1] = 9 - 10 = -1.\n        - Health becomes negative, so we do not proceed in this direction.\n    - Move Down (to (1, 0)):\n        - New remaining health: node - grid[1][0] = 9 - 4 = 5.\n        - Since 5 > 0 and 5 > maxH[1][0] (-1), update maxH[1][0] to 5 and add (5, (1, 0)) to the queue.\n        - maxH = [[9, -1, -1],        [5, -1, -1],        [-1, -1, -1]]\n        - Queue: q = [(5, (1, 0))].\n    - Move Left (out of bounds), ignore.\n    - Move Up (out of bounds), ignore.\n\n5. BFS Iteration 2\n    - Pop from the queue: node = 5, xval = 1, yval = 0.\n    - Check four possible directions (up, down, left, right) from (1, 0):\n        - Move Right (to (1, 1)):\n            - New remaining health: node - grid[1][1] = 5 - 5 = 0.\n            - Health is 0, so we cannot move forward in this direction.\n        - Move Down (to (2, 0)):\n            - New remaining health: node - grid[2][0] = 5 - 3 = 2.\n            - Since 2 > 0 and 2 > maxH[2][0] (-1), update maxH[2][0] to 2 and add (2, (2, 0)) to the queue\n            - maxH = [[9, -1, -1],        [5, -1, -1],        [2, -1, -1]]\n            - Queue: q = [(2, (2, 0))].\n        - Move Left (to (1, -1), out of bounds), ignore.\n        - Move Up (back to (0, 0)):\n            - New remaining health: node - grid[0][0] = 5 - 1 = 4.\n            - Since 4 > 0 but 4 <= maxH[0][0] (9), no update is made.\n\n6. BFS Iteration 3\n    - Pop from the queue: node = 2, xval = 2, yval = 0.\n    -   Check four possible directions (up, down, left, right) from (2, 0):\n        - Move Right (to (2, 1)):\n            - New remaining health: node - grid[2][1] = 2 - 1 = 1.\n            - Since 1 > 0 and 1 > maxH[2][1] (-1), update maxH[2][1] to 1 and add (1, (2, 1)) to the queue.\n            - maxH = [[9, -1, -1],        [5, -1, -1],        [2, 1, -1]]\n            - Queue: q = [(1, (2, 1))].\n        - Move Down (out of bounds), ignore.\n        - Move Left (to (2, -1), out of bounds), ignore.\n        - Move Up (back to (1, 0)):\n            - New remaining health: node - grid[1][0] = 2 - 4 = -2.\n            - Health becomes negative, so we do not proceed.\n        \n7. BFS Iteration 4\n    - Pop from the queue: node = 1, xval = 2, yval = 1.\n    - Check four possible directions (up, down, left, right) from (2, 1):\n        - Move Right (to (2, 2)):\n            - New remaining health: node - grid[2][2] = 1 - 1 = 0.\n            - Health is 0, so we cannot move forward in this direction.\n        - Move Down (out of bounds), ignore.\n        - Move Left (back to (2, 0)):\n            - New remaining health: node - grid[2][0] = 1 - 3 = -2.\n            - Health becomes negative, so we do not proceed.\n        - Move Up (back to (1, 1)):\n            - New remaining health: node - grid[1][1] = 1 - 5 = -4.\n            - Health becomes negative, so we do not proceed.\n\nIn no iterations, did we reach grid[2][2] with health>=1 hence we return $false$.\n\n# Complexity\n- Time complexity:-$O(n*m)$\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:$O(n*m)$\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\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>>maxH(n,vector<int>(m,-1));\n        queue<pair<int,pair<int,int>>>q;\n        q.push({health-grid[0][0],{0,0}});\n        maxH[0][0]=health;\n        while(!q.empty())\n        {\n            int node=q.front().first;\n            int xval=q.front().second.first;\n            int yval=q.front().second.second;\n            q.pop();\n            /*\n            if(xval==n-1 && yval==m-1)\n            {\n                if(node>=1)\n                    return true;\n                continue;\n            }\n            */\n            int dx[]={-1,0,1,0};\n            int dy[]={0,1,0,-1};\n            for(int i=0;i<4;++i)\n            {\n                int nx=xval+dx[i];\n                int ny=yval+dy[i];\n                if(nx>=0 && nx<n && ny>=0 && ny<m)\n                {\n                    int temp=node-grid[nx][ny];\n                    if(nx==n-1 && ny==m-1)\n                    {\n                        //--temp;\n                        if(temp>=1)\n                            return true;\n                    }\n                    if(temp>0 && temp>maxH[nx][ny])\n                    {\n                        maxH[nx][ny]=temp;\n                        q.push({temp,{nx,ny}});\n                    }\n                }\n            }\n        }\n        return false;\n    }\n};\n```
['Breadth-First Search', 'Graph', 'C++']