拜访

拜访

题目描述

现在有一个城市销售经理，需要从公司出发，去拜访市内的商家，已知他的位置以及商家的位置，但是由于城市道路交通的原因，他只能在左右中选择一个方向，在上下中选择一个方向，现在问他有多少种方案到达商家地址。

给定一个地图map及它的长宽n和m，其中1代表经理位置，2代表商家位置，-1代表不能经过的地区，0代表可以经过的地区，请返回方案数，保证一定存在合法路径。保证矩阵的长宽都小于等于10。

测试样例：

[[0,1,0],[2,0,0]],2,3

返回：2

牛客网题解：

链接：https://www.nowcoder.com/questionTerminal/12cbdcdf5d1e4059b6ddd420de6342b6
来源：牛客网

想说的是题目描述有点模糊，通过测试才发现，“他只能在左右中选择一个方向，在上下中选择一个方向”应该理解为：左右中只能选一个方向，若选择左只能一直向左走。上下中只能选择一个方向，若选择下只能一直向下。

解题思路：

1.首先找到1和2的位置，这里要注意一点，从1走到2与从2走到1所得的路径数相同，即以1为起点或以2为起点是等价的。所以我做的处理是，统一从行坐标小的位置走到行坐标大的位置，即向下走。

2.1和2的相对位置可以归纳如下：

（1）两者位于主对角线上

（2）两者位于副对角线上

（3）两者位置重合或处于同一行或同一列（该特殊情形可以合并到（1）（2）中）

3.接下来的问题就是分别对向左走和向右走的情形应用动态规划求解。

4.代码如下，已AC。

public int countPath(int[][] map, int n, int m) {
    // 首先找出1和2所在的位置
    int i,j;
    int x1=0,x2 = 0,y1 = 0,y2 = 0;
    for (i = 0; i < n; i++) {
        for (j = 0; j < m; j++) {
            if(map[i][j]==1){
                x1 = i;y1=j;
            }else if(map[i][j]==2){
                x2=i;y2=j;
            }
        }
    }      
    if(x1==x2&&y1==y2){// 两点重合
        return 1;
    }
    if(x1>x2){// x1,y1用于保存行下标的较小者
        x1 = x1^x2^(x2=x1);
        y1 = y1^y2^(y2=y1);
    }
    int dp[][] = new int[n][m];
    if(y1<y2){// 两点处在主对角线上
        dp[x1][y1] = 1;
        for (i = x1+1; i<=x2; i++) {
            dp[i][y1] = map[i][y1]==-1?0:dp[i-1][y1];
        }
        for (j = y1+1; j <=y2; j++) {
            dp[x1][j] = map[x1][j]==-1?0:dp[x1][j-1];
        }
        for (i = x1+1; i <= x2; i++) {
            for (j = y1+1; j <=y2; j++) {
                dp[i][j] = map[i][j]==-1?0:dp[i-1][j]+dp[i][j-1];
            }
        }
    }else{// 两者处在副对角线上
        dp[x1][y1] = 1;
        for (i = x1+1; i<=x2; i++) {
            dp[i][y1] = map[i][y1]==-1?0:dp[i-1][y1];
        }
        for (j = y1-1; j >=y2; j--) {
            dp[x1][j] = map[x1][j]==-1?0:dp[x1][j+1];
        }
        for (i = x1+1; i <= x2; i++) {
            for (j = y1-1; j >=y2; j--) {
                dp[i][j] = map[i][j]==-1?0:dp[i-1][j]+dp[i][j+1];
            }
        }
    }
    return dp[x2][y2];
}