一、问题描述
给定一个二维数组。
- 数组只有一个元素是1,是起点
- 数组只有一个元素是2,是终点
- 数组中的0是必须经过的地方
- 数组中的-1是障碍不可通过
从起始点到终点一共有多少路径?
二、思路
DFS
三、Code
package algorithm; /** * Created by adrian.wu on 2019/2/27. */ public class UniquePathIII { private int sr, sc, er, ec, res, empty = 0; public int uniquePathIII(int[][] grid) { for (int i = 0; i < grid.length; i++) { for (int j = 0; j < grid[0].length; j++) { if (grid[i][j] == 0) empty++; else if (grid[i][j] == 1) { sr = i; sc = j; } else if (grid[i][j] == 2) { er = i; ec = j; empty++; } } } dfs(grid, sr, sc); return res; } private void dfs(int[][] grid, int i, int j) { if (!validRange(grid, i, j)) return; if (i == er && j == ec && empty == 0) { res++; return; } grid[i][j] = -2; empty--; dfs(grid, i + 1, j); dfs(grid, i - 1, j); dfs(grid, i, j + 1); dfs(grid, i, j - 1); grid[i][j] = 0; empty++; } private boolean validRange(int[][] grid, int i, int j) { return i >= 0 && i < grid.length && j >= 0 && j < grid[0].length && grid[i][j] >= 0; } }