题目很简单，注意方向只能选左右中的一个和上下中的一个，既然要走到目的地，那么方向已经决定了，就是尽量靠近目的地。
分析：红色的圈表示起点，红色三角形表示终点。这里如果向上走或者向右走，那么永远到不了终点，所以路径只会在两个点构成的矩形中，并且方向只有两个。
按照上图，假设向左走，走一步到绿色圈的位置，或者向下走一步到蓝色的圈的位置（这里暂时假设没有障碍），对于这两种走法，都会形成一个新的移动矩形（用不同颜色表示），子问题的解组成原问题的解，动态规划。
设水平和垂直移动方向分别为v(左移为-1，右移为1，有障碍为0)和h，从起点坐标(x,y)到终点坐标(desX,desY)的方案数为f(x,y)，则有下面状态转移方程：
有了这个，代码就很容易了：
1 public int countPath(int[][] map, int n, int m) { 2 int x = 0, y = 0, desX = 0, desY = 0; 3 int vertical; 4 int horizontal; 5 for (int i = 0; i < n; i++) { // 搜索起点和终点 6 for (int j = 0; j < m; j++) { 7 if (map[i][j] == 1) { 8 x = i; 9 y = j; 10 } 11 if (map[i][j] == 2) { 12 desX = i; 13 desY = j; 14 } 15 } 16 } 17 if (desX == x) { // 设定递归终止条件 18 for (int i = Math.min(y, desY); i <= Math.max(y, desY); i++) { 19 if (map[x][i] == -1) { // 直线路径上是否有障碍 20 return 0; 21 } 22 } 23 return 1; 24 } 25 if (desY == y) { 26 for (int i = Math.min(x, desX); i < Math.max(x, desX); i++) { 27 if (map[i][y] == -1) { 28 return 0; 29 } 30 } 31 return 1; 32 } 33 horizontal = desX - x > 0 ? 1 : -1; // 确定水平方向 34 vertical = desY - y > 0 ? 1 : -1; // 确定垂直方向 35 int[][] ver = new int[map.length][]; 36 for (int i = 0; i < ver.length; i++) { 37 ver[i] = map[i].clone(); // 逐层拷贝，否则引用会和下面的数组相同 38 } 39 ver[x][y] = 0; 40 ver[x + vertical][y] = 1; 41 int[][] hor = new int[map.length][]; 42 for (int i = 0; i < hor.length; i++) { 43 hor[i] = map[i].clone(); 44 } 45 hor[x][y] = 0; 46 hor[x][y + horizontal] = 1; 47 if (map[x + vertical][y] == -1) { // 判断水平路径是否合法，即是否能水平移动 48 return countPath(hor, n, m); // 如不能，则只垂直移动 49 } 50 if (map[x][y + horizontal] == -1) { 51 return countPath(ver, n, m); 52 } 53 return countPath(ver, n, m) + countPath(hor, n, m); // 如果方向没限制，则结果为水平走和垂直的和 54 }
因为要把移动了之后的数组传入递归方法，所以需要对数组进行clone操作，这里不能直接对二维数组进行clone操作，需要通过for循环逐层拷贝，否则会因为引用相同而使得ver和hor数组的内容相同。