不同路径一

矩形格，左上角 到 右下角。

class Solution {int [] directX = new int[]{-1,1,0,0};int [] directY = new int[]{0,0,-1,1};int rows;int cols;public int uniquePathsIII(int[][] grid) {if (grid == null || grid.length == 0 || grid[0].length == 0) {return 0;}// dfs + 回溯int startX = 0;int startY = 0;int stepNeed = 1;rows = grid.length;cols = grid[0].length;for (int i = 0; i < rows; i++) {for (int j = 0; j < cols; j++) {if (grid[i][j] == 1){startX = i;startY = j;continue;}if (grid[i][j] == 0) stepNeed ++;}}return dfs(startX,startY,stepNeed,grid);}private int dfs(int x, int y, int stepNeed, int[][] grid) {// terminalif (grid[x][y] == -1) return 0;if (grid[x][y] == 2) return stepNeed == 0 ? 1 : 0;// process logic and drill downgrid[x][y] = -1;int count = 0;for (int i = 0; i < 4; i++) {int newX = x + directX[i];int newY = y + directY[i];if (newX < 0 || newX >= rows || newY < 0 || newY >= cols) continue;count += dfs(newX,newY,stepNeed - 1,grid);}// reversegrid[x][y] = 0;return count;}}

不同路径二

不同路径三