现在有一个城市销售经理，需要从公司出发，去拜访市内的商家，已知他的位置以及商家的位置，但是由于城市道路交通的原因，他只能在左右中选择一个方向，在上下中选择一个方向，现在问他有多少种方案到达商家地址。
给定一个地图map及它的长宽n和m，其中1代表经理位置，2代表商家位置，-1代表不能经过的地区，0代表可以经过的地区，请返回方案数，保证一定存在合法路径。保证矩阵的长宽都小于等于10。
测试样例： [[0,1,0],[2,0,0]],2,3 返回：2思路：参考自https://www.nowcoder.com/profile/7491640/codeBookDetail?submissionId=17004341
通过测试才发现，“他只能在左右中选择一个方向，在上下中选择一个方向”应该理解为：左右中只能选一个方向，若选择左只能一直向左走。上下中只能选择一个方向，若选择下只能一直向下。
解题思路： 1.首先找到1和2的位置，这里要注意一点，从1走到2与从2走到1所得的路径数相同，即以1为起点或以2为起点是等价的。所以我做的处理是，统一从行坐标小的位置走到行坐标大的位置，即向下走。 2.1和2的相对位置可以归纳如下： （1）两者位于主对角线上 （2）两者位于副对角线上 （3）两者位置重合或处于同一行或同一列（该特殊情形可以合并到（1）（2）中） 3.接下来的问题就是分别对向左走和向右走的情形应用动态规划求解。 #include<iostream> #include<map> #include<vector> using namespace std; class Visit { public: int countPath(vector<vector<int> > map, int n, int m) { // write code here int x1 = 0, x2 = 0, y1 = 0, y2 = 0; //找出1和2的位置点 for (int i = 0; i<n; i++) { for (int j = 0; j<m; j++) { if (map[i][j] == 1) { x1 = i; y1 = j; } if (map[i][j] == 2) { x2 = i; y2 = j; } } } //使x1，y1代表的是上方的位置 if (x1 == x2&&y1 == y2) return 1; if (x1>x2) { int x = x1; x1 = x2; x2 = x; int y = y1; y1 = y2; y2 = y; } int dp[10][10]; dp[x1][y1] = 1; //主对角线 if (y1<y2) { for (int x = x1 + 1; x <= x2; x++) { if (map[x][y1] != -1) dp[x][y1] = dp[x - 1][y1]; else dp[x][y1] = 0; } for (int y = y1 + 1; y <= y2; y++) { if (map[x1][y] != -1) dp[x1][y] = dp[x1][y - 1]; else dp[x1][y] = 0; } for (int x = x1 + 1; x <= x2; x++) { for (int y = y1 + 1; y <= y2; y++) { if (map[x][y] != -1) dp[x][y] = dp[x][y - 1] + dp[x - 1][y]; else dp[x][y] = 0; } } } else //负对角线 { for (int x = x1 + 1; x <= x2; x++) { if (map[x][y1] != -1) dp[x][y1] = dp[x - 1][y1]; else dp[x][y1] = 0; } for (int y = y1 - 1; y >= y2; y--) { if (map[x1][y] != -1) dp[x1][y] = dp[x1][y + 1]; else dp[x1][y] = 0; } for (int x = x1 + 1; x <= x2; x++) { for (int y = y1 - 1; y >= y2; y--) { if (map[x][y] != -1) dp[x][y] = dp[x][y + 1] + dp[x - 1][y]; else dp[x][y] = 0; } } } int result = dp[x2][y2]; //delete[] dp; return result; } }; int main() { Visit s; int n, m; cin >> n >> m; vector<vector<int> > map(n, vector<int>()); for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { int number; cin >> number; map[i].push_back(number); } } int count=s.countPath(map,n,m); cout << count << endl; }