package leetcode;

/**
 * https://leetcode.com/problems/unique-paths-iii/
 */
public class Problem980 {
    public int uniquePathsIII(int[][] grid) {
        // TODO
        return 0;
    }

    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
    }
}

@@ -155,15 +155,1392 @@
     
-// TODO
+int maxRow = grid.length;%0A        int maxCol = maxRow %3E 0 ? grid%5B0%5D.length : 0;%0A        int row = 0;%0A        int col = 0;%0A        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 == 1) %7B%0A                    row = i;%0A                    col = j;%0A                    break;%0A                %7D%0A            %7D%0A        %7D%0A        return uniquePaths(grid, maxRow, maxCol, row, col);%0A    %7D%0A%0A    private static int uniquePaths(int%5B%5D%5B%5D grid, int maxRow, int maxCol, int row, int col) %7B%0A        if (row %3C 0 %7C%7C row == maxRow %7C%7C col %3C 0 %7C%7C col == maxCol) %7B%0A            return 0;%0A        %7D%0A        if (grid%5Brow%5D%5Bcol%5D == -1 %7C%7C grid%5Brow%5D%5Bcol%5D == 3) %7B%0A            return 0;%0A        %7D%0A        if (grid%5Brow%5D%5Bcol%5D == 2) %7B%0A            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;%0A        %7D%0A        grid%5Brow%5D%5Bcol%5D = 3;%0A        int a = uniquePaths(grid, maxRow, maxCol, row - 1, col); // up%0A        int b = uniquePaths(grid, maxRow, maxCol, row, col + 1); // right%0A        int c = uniquePaths(grid, maxRow, maxCol, row + 1, col); // down%0A        int d = uniquePaths(grid, maxRow, maxCol, row, col - 1); // left%0A        grid%5Brow%5D%5Bcol%5D = 0; // backtrack
 %0A   
@@ -1547,25 +1547,36 @@
      return 
-0
+a + b + c+ d
 ;%0A    %7D%0A%0A   

Update problem 980