Brute Force -> Optimal Solution | DFS + BFS | Easy C++ solution
Intuition\n Describe your first thoughts on how to solve this problem. \nThe intuition behind this problem is to use BFS to explore all possible paths from the 
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nThe intuition behind this problem is to use BFS to explore all possible paths from the top-left to the bottom-right corner while managing health, which decreases when stepping on unsafe cells (`grid[i][j] == 1`). BFS ensures the shortest path exploration, and we track the maximum health at each cell to avoid revisiting paths with lower health. If the health drops to zero or below at any point, that path is invalid. The goal is to determine if we can reach the bottom-right corner with positive health.\n# Approach\n<!-- Describe your approach to solving the problem. -->\nHere\'s a stepwise approach to solving the problem:\n\n1. **Initialize BFS**:\n   - Start from the top-left corner `(0, 0)` with the given `health`.\n   - If the starting cell is unsafe (`grid[0][0] == 1`), reduce health by 1.\n\n2. **Edge Case Check**:\n   - If health becomes 0 or less after the first step, return `false`.\n\n3. **BFS Setup**:\n   - Use a queue to track the current position and remaining health.\n   - Maintain a `visited` array to store the maximum health when visiting each cell.\n\n4. **Explore Neighboring Cells**:\n   - For each cell, explore its four neighbors (up, down, left, right).\n   - If moving to a neighbor reduces health but health is still positive, continue.\n   - Only move to the neighbor if the current path offers more health than previous visits.\n\n5. **Check for End**:\n   - If you reach the bottom-right corner with positive health, return `true`.\n\n6. **Return Result**:\n   - If no valid path is found, return `false`.\n\n# Brute Force(DFS try all possible paths)\n```cpp []\nclass Solution {\npublic:\n    bool canReachEnd(int x, int y, vector<vector<int>>& grid, int health, vector<vector<bool>>& visited) {\n        int m = grid.size();\n        int n = grid[0].size();\n        \n        // Base case: Reached bottom-right corner with positive health\n        if (x == m - 1 && y == n - 1 && health > 0) {\n            return true;\n        }\n        \n        // Base case: Out of bounds or health is not positive\n        if (x < 0 || x >= m || y < 0 || y >= n || health <= 0) {\n            return false;\n        }\n        \n        // Base case: Already visited cell\n        if (visited[x][y]) {\n            return false;\n        }\n        \n        // Mark this cell as visited\n        visited[x][y] = true;\n        \n        // Calculate new health after stepping on this cell\n        int newHealth = health - (grid[x][y] == 1 ? 1 : 0);\n        \n        // Explore all four directions\n        bool result = canReachEnd(x + 1, y, grid, newHealth, visited) || // Down\n                      canReachEnd(x - 1, y, grid, newHealth, visited) || // Up\n                      canReachEnd(x, y + 1, grid, newHealth, visited) || // Right\n                      canReachEnd(x, y - 1, grid, newHealth, visited);   // Left\n        \n        // Unmark this cell (optional, if using global visited)\n        visited[x][y] = false;\n        \n        return result;\n    }\n    \n    bool findSafeWalk(vector<vector<int>>& grid, int health) {\n        int m = grid.size();\n        int n = grid[0].size();\n        vector<vector<bool>> visited(m, vector<bool>(n, false));\n        \n        // Handle the starting cell\n        if (grid[0][0] == 1) {\n            health--; // Adjust health if starting cell is unsafe\n        }\n        \n        // If health is non-positive at the start, no valid path\n        if (health <= 0) {\n            return false;\n        }\n        \n        return canReachEnd(0, 0, grid, health, visited);\n    }\n};\n```\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n$$O(exponential)$$\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n$$O(m*n)$$\n\n# Optimal Solution(BFS)\n```cpp []\nclass Solution {\npublic:\n    bool findSafeWalk(vector<vector<int>>& grid, int health) {\n        int m = grid.size();\n        int n = grid[0].size();\n        vector<pair<int, int>> dir = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};\n        queue<pair<pair<int, int>, int>> q;\n        vector<vector<int>> vis(m, vector<int>(n, -1));\n        if (grid[0][0] == 1) {\n            health--;\n        }\n        if (health <= 0) return false; \n        q.push({{0, 0}, health});\n        vis[0][0] = health;\n        while (!q.empty()) {\n            auto [pos, currHealth] = q.front();\n            auto [x, y] = pos;\n            q.pop();\n            if (x == m - 1 && y == n - 1 && currHealth > 0) {\n                return true;\n            }\n            for (auto [dx, dy] : dir) {\n                int newX = x + dx;\n                int newY = y + dy;\n                if (newX >= 0 && newX < m && newY >= 0 && newY < n) {\n                    int newHealth = currHealth - (grid[newX][newY] == 1 ? 1 : 0);\n                    if (newHealth > 0 && newHealth > vis[newX][newY]) {\n                        q.push({{newX, newY}, newHealth});\n                        vis[newX][newY] = newHealth;\n                    }\n                }\n            }\n        }\n        return false;\n    }\n};\n\n```\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n$$O(m*n)$$\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n$$O(m*n)$$
['Breadth-First Search', 'Queue', 'Matrix', 'C++']