C++ Solution || BFS Approach || Full Explanation
Intuition\nThe problem is to determine if there is a path from the top-left to the bottom-right corner of a grid where we start with a given amount of health. M
# Intuition\n*The problem is to determine if there is a path from the top-left to the bottom-right corner of a grid where we start with a given amount of health. Moving through unsafe cells (represented by 1) decreases health by 1. The goal is to find if a safe path exists such that the remaining health is positive upon reaching the destination.*\n\n# Approach\n*We use BFS approach to explore all possible paths from the start cell (0, 0) to the end cell (n-1, m-1) in the grid. The BFS ensures that we explore all potential paths level by level, and efficiently finds the shortest path.*\n\n\n**Step-1 : Base Condition**\n 1. If the starting cell (0, 0) is unsafe, reduce the initial health.\n 2. If the updated health is less than 1, it\'s impossible to start the journey, so return false.\n\n**Step-2 : Initialisation**\n1. Maintain a vis matrix to store the maximum health remaining when reaching each cell. This ensures that cells are revisited only if a better (higher health) state can be achieved.\n\n- *(For example: If i visit cell(1,1) with health 5 and lets consider the answer through this path is false. So if health 5 could not lead to destination then there is no-way health 4 and so on reach out the destination.)*\n\n2. Use a queue to implement BFS. The contents in Queue are x,y,health. \n\n# Complexity\n- **Time complexity:**\n*Worst-Case: Each cell is processed once per possible health state. Therefore, the time complexity is O(n * m * H), where n is the number of rows, m is the number of columns, and H is the maximum health. This is because each state (x, y, health) is processed once.*\n\n- **Space complexity:**\n*The primary space usage is from the vis matrix and the BFS queue. The queue can store up to O(n * m * H) states in the worst case. Therefore, the space complexity is O(n * m * H).*\n\n# Code\n```cpp []\n#include <queue>\nclass Solution {\n\n    vector<pair<int, int>> dir = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}}; \n\npublic:\n    bool findSafeWalk(vector<vector<int>>& grid, int health) {\n        int n = grid.size();\n        int m = grid[0].size();\n        \n        if (grid[0][0] == 1) health--; \n        \n        if (health < 1) return false; \n\n        queue<pair<pair<int,int>,int>> q;\n        q.push({{0, 0}, health});\n\n        vector<vector<int>> vis(n, vector<int>(m, -1)); \n        vis[0][0] = health;\n\n        while (!q.empty()) {\n            int x = q.front().first.first ;\n            int y = q.front().first.second ;\n            int health = q.front().second ;\n            q.pop();\n\n            if (x == n - 1 && y == m - 1) return true; \n\n            for (auto it : dir) {\n                int n_x = x + it.first;\n                int n_y = y + it.second;\n\n                if (n_x >= 0 && n_x < n && n_y >= 0 && n_y < m) {\n                    int newHealth = health;\n\n                    if (grid[n_x][n_y] == 1) newHealth--;\n\n   \n                    if (newHealth > 0 && newHealth > vis[n_x][n_y]) {\n                        vis[n_x][n_y] = newHealth; \n                        q.push({{n_x, n_y}, newHealth});\n                    }\n                }\n            }\n        }\n\n        return false; \n    }\n};\n\n```\n\nThis question can also be done using dfs and then memoization.\n\nIf you found this solution helpful, please consider upvoting it. Your feedback is greatly appreciated!
['Breadth-First Search', 'C++']