首页 > 代码库 > 拜访-动态规划
拜访-动态规划
现在有一个城市销售经理，需要从公司出发，去拜访市内的商家，已知他的位置以及商家的位置，但是由于城市道路交通的原因，他只能在左右中选择一个方向，在上下中选择一个方向，现在问他有多少种方案到达商家地址。
给定一个地图map及它的长宽n和m，其中1代表经理位置，2代表商家位置，-1代表不能经过的地区，0代表可以经过的地区，请返回方案数，保证一定存在合法路径。保证矩阵的长宽都小于等于10。
测试样例：
[[0,1,0],[2,0,0]],2,3
返回：2
1 lass Visit { 2 public: 3 4 5 int countPath(vector<vector<int> > map, int n, int m) { 6 // write code here 7 int x1,y1; 8 int x2,y2; 9 for(int i=0;i<n;i++)10 {11 for(int j=0;j<m;j++)12 {13 if(map[i][j]==1)14 {15 x1=i;16 y1=j;17 }18 if(map[i][j]==2)19 {20 x2=i;y2=j;21 }22 }23 }24 if(x1==x2&&y1==y2)25 return 0;26 int xt=x1<x2?1:-1;27 int yt=y1<y2?1:-1;28 vector<vector<int>>dp(n,vector<int>(m,1));29 for(int i=x1+xt;i!=(x2+xt);i+=xt)30 {31 dp[i][y1]=map[i][y1]==-1?0:dp[i-xt][y1];32 }33 for(int j=y1+yt;j!=(y2+yt);j+=yt)34 {35 dp[x1][j]=map[x1][j]==-1?0:dp[x1][j-yt];36 }37 for(int i=x1+xt;i!=(x2+xt);i+=xt)38 {39 for(int j=y1+yt;j!=(y2+yt);j+=yt)40 {41 dp[i][j]=map[i][j]==-1?0:dp[i-xt][j]+dp[i][j-yt];42 }43 }44 return dp[x2][y2];45 }46 };
矩阵1
0 0 1 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 2 0
dp
0 0 1 1 1 0
0 0 1 0 0 0
0 0 1 0 0 0
0 0 1 0 0 0
0 0 1 0 0 0
dp[i][j]=dp[i-1][j]+dp[i][j-1]
0 0 1 1 1 0
0 0 1 2 3 0
0 0 1 3 6 0
0 0 1 4 10 0
0 0 1 5 15 0
拜访-动态规划
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。