package com.wujunshen.algorithm.leetcode.backtracking;

/**
 * @author frank woo(吴峻申) <br>
 * email:<a href="mailto:frank_wjs@hotmail.com">frank_wjs@hotmail.com</a> <br>
 * @date 2022/7/30 21:58<br>
 */
public class 不同路径III {
    public int uniquePathsIII(int[][] grid) {
        //当grid[i][j] == 2, stepNum++, 这里直接初始化为1
        int startX = 0;
        int startY = 0;
        int stepNum = 1;
        //遍历获取起始位置和统计总步数
        for (int i = 0; i < grid.length; i++){
            for (int j = 0; j < grid[0].length; j++){
                if (grid[i][j] == 1){
                    startY = i;
                    startX = j;
                    continue;
                }
                if (grid[i][j] == 0) {
                    stepNum++;
                }
            }
        }

        return dfs(startX, startY, stepNum, grid);
    }

    private int dfs(int x, int y, int stepNum, int[][] grid){
        //排除越界的情况和遇到障碍的情况
        if (x < 0 || x >= grid[0].length || y < 0 || y >= grid.length || grid[y][x] == -1) {
            return 0;
        }
        if (grid[y][x] == 2) {
            return stepNum == 0 ? 1 : 0;
        }
        //已走过的标记为障碍
        grid[y][x] = -1;
        int res = 0;
        res += dfs(x - 1, y, stepNum - 1, grid);
        res += dfs(x + 1, y, stepNum - 1, grid);
        res += dfs(x, y - 1, stepNum - 1, grid);
        res += dfs(x, y + 1, stepNum - 1, grid);
        //dfs遍历完该位置为起始位置的情况后，置零，以不影响后面的dfs
        grid[y][x] = 0;
        return res;
    }
}