✅Beats 100%🔥C++🔥Java🔥Python🔥BFS🚀Detailed Explanation
Problem Overview\nYou need to determine if there\'s a path from the top-left corner to the bottom-right corner of a grid, where moving through cells with 1 decr
### Problem Overview\nYou need to determine if there\'s a path from the top-left corner to the bottom-right corner of a grid, where moving through cells with `1` decreases your health. You start with a given amount of health, and you need to ensure that you reach the destination with a positive health value.\n\n### Solution Explanation\n\nThe solution uses a modified Breadth-First Search (BFS) to explore the grid, leveraging two queues to handle cells based on their safety status. The approach is inspired by the 0-1 BFS algorithm, which efficiently handles graphs with edge weights of 0 and 1.\n\n### Key Components\n\n1. **Grid Initialization**:\n   - `cost`: A 2D vector to keep track of the maximum health value remaining when reaching each cell. Initially set to -1 for all cells.\n\n2. **Two Queues**:\n   - `ZERO`: For cells that do not reduce health (`grid[y][x] == 0`).\n   - `ONE`: For cells that reduce health (`grid[y][x] == 1`).\n\n3. **Push Function**:\n   - `push(y, x, c)`: Updates the cost of reaching cell `(y, x)` if the new computed cost `c` is higher than the previously recorded cost. Depending on whether the cell is safe or unsafe, it pushes the cell to the appropriate queue.\n\n### BFS Process\n\n1. **Initialization**:\n   - Start from the top-left corner `(0, 0)`. Calculate the initial health after stepping on the starting cell and push it to the appropriate queue.\n\n2. **Processing Queues**:\n   - **Zero Queue**: Process cells from the `ZERO` queue first because they are safer (do not reduce health). Update adjacent cells based on the current cell\'s cost.\n   - **One Queue**: Once the `ZERO` queue is empty, process cells from the `ONE` queue. These cells reduce health, so this step ensures that all possible safe paths are explored.\n\n3. **Update Adjacent Cells**:\n   - For each cell, explore its four possible neighbors (up, down, left, right). Calculate the new health cost for reaching each neighbor and update if it\'s beneficial.\n\n4. **Check Destination**:\n   - After processing all possible cells, check if the cost to reach the bottom-right corner `(n-1, m-1)` is positive.\n\n### Code Implementation\n\nHere\u2019s a solution for the problem in Python, C++, and Java, with detailed explanations for each.\n\n### Python\n\n``` python []\nclass Solution:\n    def findSafeWalk(self, grid: List[List[int]], h: int) -> bool:\n        m = len(grid)\n        n = len(grid[0])\n        vis = [[0 for _ in range(n)] for _ in range(m)]\n        memo = {}\n        def dfs(x,y,ans):\n            if x<0 or x>=m or y>=n or y<0 or vis[x][y]==1 or ans>=h:\n                return float(\'inf\')\n\n            if x==m-1 and y==n-1:\n                return ans+grid[x][y]\n\n            if (x,y,ans) in memo:\n                return memo[(x,y,ans)]\n\n            vis[x][y] = 1\n            \n            memo[(x,y,ans)] = min(dfs(x+1,y,ans+grid[x][y]),dfs(x-1,y,ans+grid[x][y]),dfs(x,y+1,ans+grid[x][y]),dfs(x,y-1,ans+grid[x][y]))\n            vis[x][y] = 0\n            return memo[(x,y,ans)]\n        a = dfs(0,0,0)\n        return a-h<0\n#aijcoder\n```\n\n```cpp []\n#include <vector>\n#include <queue>\n\nusing namespace std;\n\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>> cost(n, vector<int>(m, -1));\n        queue<pair<int, int>> ZERO, ONE;\n        \n        auto push = [&](int y, int x, int c) {\n            if (cost[y][x] < c) {\n                if (grid[y][x]) ONE.push({y, x});\n                else ZERO.push({y, x});\n                cost[y][x] = c;\n            }\n        };\n        \n        push(0, 0, health - grid[0][0]);\n        \n        int dy[4] = {-1, 0, 1, 0};\n        int dx[4] = {0, 1, 0, -1};\n        \n        while (!ZERO.empty() || !ONE.empty()) {\n            while (!ZERO.empty()) {\n                auto [y, x] = ZERO.front(); ZERO.pop();\n                for (int i = 0; i < 4; ++i) {\n                    int ny = y + dy[i], nx = x + dx[i];\n                    if (0 <= ny && ny < n && 0 <= nx && nx < m) {\n                        push(ny, nx, cost[y][x] - grid[ny][nx]);\n                    }\n                }\n            }\n            while (!ONE.empty() && ZERO.empty()) {\n                auto [y, x] = ONE.front(); ONE.pop();\n                for (int i = 0; i < 4; ++i) {\n                    int ny = y + dy[i], nx = x + dx[i];\n                    if (0 <= ny && ny < n && 0 <= nx && nx < m) {\n                        push(ny, nx, cost[y][x] - grid[ny][nx]);\n                    }\n                }\n            }\n        }\n        \n        return cost[n - 1][m - 1] > 0;\n    }\n};\n```\n```java []\nclass Solution {\n    public boolean findSafeWalk(List<List<Integer>> grid, int health) {\n        int n = grid.size();\n        int m = grid.get(0).size();\n        \n        int[] dr = new int[] {0, 0, 1, -1};\n        int[] dc = new int[] {1, -1, 0, 0};\n        \n        boolean[][][] visited = new boolean[n][m][health + 1];\n        Queue<int[]> bfs = new LinkedList<>();\n        \n        bfs.add(new int[]{0, 0, health - grid.get(0).get(0)});\n        visited[0][0][health - grid.get(0).get(0)] = true;\n        \n        while(!bfs.isEmpty()) {\n            int size = bfs.size();\n            while(size-- > 0) {\n                int[] currNode = bfs.poll();\n                int r = currNode[0];\n                int c = currNode[1];\n                int h = currNode[2];\n               \n                if(r == n-1 && c == m-1 && h > 0) {\n                    return true;\n                }\n                 \n                for(int k = 0; k < 4; k++) {\n                    int nr = r + dr[k];\n                    int nc = c + dc[k];\n                    if(isValidMove(nr, nc, n, m)) {\n                        int nh = h - grid.get(nr).get(nc);\n                        if(nh >= 0 && visited[nr][nc][nh] == false) {\n                            visited[nr][nc][nh] = true;\n                            bfs.add(new int[]{nr, nc, nh});\n                        }\n                    }\n                }\n            }\n        }\n        \n        return false;\n    }\n    \n    private boolean isValidMove(int r, int c, int n, int m) {\n        return r >= 0 && c >= 0 && r < n && c < m;\n    }\n}\n```\n\n### Summary\n- **Initialization**: Set up cost tracking and queues.\n- **BFS**: Process cells based on their safety status and update costs.\n- **Termination**: Check if the destination cell has positive health.\n\nThis approach ensures that all paths are considered efficiently, taking into account both safe and unsafe cells.
['C++', 'Java', 'Python3']