题解 | #拜访#

import java.util.*;
/**
 第一个解法在讨论区用的是最短路求方案
 第二个就是就是常见的dp
    这类题简化就是从左上角->右下角的方案问题，但是这题目麻烦在于 我们知道起点，但是终点却可能在四个方向 左上 左下 右上  右下
    我们只需要转成题目变成：固定起点在左上角，然后将终点固定到右下角，然后直接dp就好了

*/
public class Visit {
    public int countPath(int[][] map, int n, int m) {
         int[][] f = new int[n + 20][m + 20];
         int x1 = 1, y1 = 1, x2 = 1, y2 = 1;
         for(int i = 0; i < n; i ++){
             for(int j = 0; j < m; j ++)
                 if(map[i][j] == 1)
                 {
                     x1 = i; y1 = j;
                 }else  if(map[i][j] == 2){
                     x2 = i; y2 = j;
                 }
         }

         int dx = x1 > x2 ? -1 : 1;
         int dy = y1 > y2 ? -1 : 1;

         if(dx == -1)
             x2 = x1 - x2 + x1;  //数学推论 没有化简 
         if(dy == -1)
             y2 = y1- y2 + y1;  //数学推论 
         //一定是往下
        // x2 y2 固定到了右下角
        f[x1][y1] = 1;
         for(int i = x1; i <= x2; i ++){ 
             for(int j = y1; j <= y2; j ++){  
                 if(i - 1 >= x1)
                     f[i][j] += f[i - 1][j];
                 if(j - 1 >= y1)
                     f[i][j] += f[i][j - 1];
             }

         }


        return f[x2][y2];






    }
}