package leetcode;

/**
 * https://leetcode.com/problems/unique-paths-iii/
 */
public class Problem980 {
    public int uniquePathsIII(int[][] grid) {
        int maxRow = grid.length;
        int maxCol = maxRow > 0 ? grid[0].length : 0;
        int row = 0;
        int col = 0;
        for (int i = 0; i < maxRow; i++) {
            for (int j = 0; j < maxCol; j++) {
                if (grid[i][j] == 1) {
                    row = i;
                    col = j;
                    break;
                }
            }
        }
        return uniquePaths(grid, maxRow, maxCol, row, col);
    }

    private static int uniquePaths(int[][] grid, int maxRow, int maxCol, int row, int col) {
        if (row < 0 || row == maxRow || col < 0 || col == maxCol) {
            return 0;
        }
        if (grid[row][col] == -1 || grid[row][col] == 3) {
            return 0;
        }
        if (grid[row][col] == 2) {
            for (int i = 0; i < maxRow; i++) {
                for (int j = 0; j < maxCol; j++) {
                    if (grid[i][j] == 0) {
                        return 0;
                    }
                }
            }
            return 1;
        }
        grid[row][col] = 3;
        int a = uniquePaths(grid, maxRow, maxCol, row - 1, col); // up
        int b = uniquePaths(grid, maxRow, maxCol, row, col + 1); // right
        int c = uniquePaths(grid, maxRow, maxCol, row + 1, col); // down
        int d = uniquePaths(grid, maxRow, maxCol, row, col - 1); // left
        grid[row][col] = 0; // backtrack
        return a + b + c+ d;
    }

    public static void main(String[] args) {
        Problem980 prob = new Problem980();
        System.out.println(prob.uniquePathsIII(new int[][]{
            {1, 0, 0, 0},
            {0, 0, 0, 0},
            {0, 0, 2, -1}
        })); // 2
        System.out.println(prob.uniquePathsIII(new int[][]{
            {1, 0, 0, 0},
            {0, 0, 0, 0},
            {0, 0, 0, 2}
        })); // 4
        System.out.println(prob.uniquePathsIII(new int[][]{
            {0, 1},
            {2, 0}
        })); // 0
    }
}

@@ -269,24 +269,47 @@
 nt col = 0;%0A
+        int steps = 0;%0A
         for 
@@ -378,32 +378,145 @@
  maxCol; j++) %7B%0A
+                if (grid%5Bi%5D%5Bj%5D == -1) %7B%0A                    continue;%0A                %7D%0A                steps++;%0A
                 
@@ -600,35 +600,8 @@
  j;%0A
-                    break;%0A
     
@@ -695,16 +695,27 @@
 row, col
+, steps - 1
 );%0A    %7D
@@ -805,16 +805,62 @@
  int col
+,%0A                                   int steps
 ) %7B%0A    
@@ -991,31 +991,8 @@
 = -1
- %7C%7C grid%5Brow%5D%5Bcol%5D == 3
 ) %7B%0A
@@ -1074,245 +1074,33 @@
     
-for (int i = 0; i %3C maxRow; i++) %7B%0A                for (int j = 0; j %3C maxCol; j++) %7B%0A                    if (grid%5Bi%5D%5Bj%5D == 0) %7B%0A                        return 0;%0A                    %7D%0A                %7D%0A            %7D%0A            return 1
+return steps == 0 ? 1 : 0
 ;%0A  
@@ -1136,9 +1136,10 @@
 %5D = 
-3
+-1
 ;%0A  
@@ -1194,24 +1194,35 @@
 row - 1, col
+, steps - 1
 ); // up%0A   
@@ -1278,16 +1278,27 @@
 w, col +
+ 1, steps -
  1); // 
@@ -1365,16 +1365,27 @@
 + 1, col
+, steps - 1
 ); // do
@@ -1447,16 +1447,27 @@
 w, col -
+ 1, steps -
  1); // 
@@ -1536,16 +1536,17 @@
  + b + c
+ 
 + d;%0A   
@@ -1551,531 +1551,7 @@
    %7D
-%0A%0A    public static void main(String%5B%5D args) %7B%0A        Problem980 prob = new Problem980();%0A        System.out.println(prob.uniquePathsIII(new int%5B%5D%5B%5D%7B%0A            %7B1, 0, 0, 0%7D,%0A            %7B0, 0, 0, 0%7D,%0A            %7B0, 0, 2, -1%7D%0A        %7D)); // 2%0A        System.out.println(prob.uniquePathsIII(new int%5B%5D%5B%5D%7B%0A            %7B1, 0, 0, 0%7D,%0A            %7B0, 0, 0, 0%7D,%0A            %7B0, 0, 0, 2%7D%0A        %7D)); // 4%0A        System.out.println(prob.uniquePathsIII(new int%5B%5D%5B%5D%7B%0A            %7B0, 1%7D,%0A            %7B2, 0%7D%0A        %7D)); // 0%0A    %7D
 %0A%7D%0A

Solve problem 980