Untitled

#include <vector>
#include <unordered_set>
#include <string>

using namespace std;

class Solution {
public:
    bool canReachDestination(vector<vector<int>>& grid, int health) {
        int m = grid.size();
        int n = grid[0].size();
        
        // Edge case checks
        if (grid[0][0] == 1 && health <= 1) {
            return false;
        }
        if (grid[m-1][n-1] == 1 && health <= 1) {
            return false;
        }
        
        // Set up the DFS function
        return dfs(grid, 0, 0, health, m, n);
    }

private:
    bool dfs(vector<vector<int>>& grid, int x, int y, int health, int m, int n) {
        // Base cases
        if (x < 0 || x >= m || y < 0 || y >= n || health <= 0) {
            return false;
        }
        if (x == m - 1 && y == n - 1) {
            return health > 0;  // Only valid if health is positive
        }
        if (grid[x][y] == 1) {
            --health;
        }

        // Mark this cell as visited by adding it to the visited set
        string cell = to_string(x) + "," + to_string(y);
        if (visited.count(cell)) {
            return false;
        }
        visited.insert(cell);

        // Explore the four possible directions
        bool result = 
            dfs(grid, x + 1, y, health, m, n) || // Move down
            dfs(grid, x - 1, y, health, m, n) || // Move up
            dfs(grid, x, y + 1, health, m, n) || // Move right
            dfs(grid, x, y - 1, health, m, n);   // Move left

        // Backtrack: Remove from visited set
        visited.erase(cell);

        return result;
    }

    unordered_set<string> visited;
};