unique path3

public class Solution {
    private int totalEmpty = 1; // Start cell is also counted
    private int result = 0;
    private int rows, cols;

    public int uniquePathsIII(int[][] grid) {
        int startX = 0, startY = 0;
        rows = grid.length;
        cols = grid[0].length;

        // Step 1: Count total empty cells and find starting cell
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (grid[i][j] == 0) {
                    totalEmpty++;
                } else if (grid[i][j] == 1) {
                    startX = i;
                    startY = j;
                }
            }
        }

        // Step 2: Start DFS from starting cell
        dfs(grid, startX, startY, 0);
        return result;
    }

    private void dfs(int[][] grid, int x, int y, int count) {
        // Check boundaries or if it's an obstacle or already visited
        if (x < 0 || y < 0 || x >= rows || y >= cols || grid[x][y] == -1) {
            return;
        }

        if (grid[x][y] == 2) {
            // Reached destination — check if we visited all empty cells
            if (count == totalEmpty) {
                result++;
            }
            return;
        }

        // Mark current cell as visited
        int temp = grid[x][y];
        grid[x][y] = -1;

        // Explore 4 directions
        dfs(grid, x + 1, y, count + 1);
        dfs(grid, x - 1, y, count + 1);
        dfs(grid, x, y + 1, count + 1);
        dfs(grid, x, y - 1, count + 1);

        // Backtrack
        grid[x][y] = temp;
    }
}