package question;

/*
    @author: Roderland
    @create: 2020-09-19---23:17
*/
public class Question980 {

    private int[][] grid;
    private int pathCount;
    private int count;

    public int uniquePathsIII(int[][] grid) {
        this.grid = grid;
        pathCount = 0;
        int x = 0;
        int y = 0;
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[i].length; j++) {
                if (grid[i][j] == 0) pathCount++;
                if (grid[i][j] == 1) {
                    x = i;
                    y = j;
                }
            }
        }
        fun(x, y);
        return count;
    }

    public void fun(int i, int j) {
        if (j + 1 < grid[i].length) partOfFun(i, j + 1);
        if (i + 1 < grid.length) partOfFun(i + 1, j);
        if (j - 1 >= 0) partOfFun(i, j - 1);
        if (i - 1 >= 0) partOfFun(i - 1, j);
    }

    private void partOfFun(int i, int j) {
        if (grid[i][j] == 0) {
            pathCount--;
            grid[i][j] = 1;
            fun(i, j);
            grid[i][j] = 0;
            pathCount++;
        } else if (grid[i][j] == 2 && pathCount == 0) count++;
    }

}