KeyWolf

用户名：17354378026

访问量：16440

签　名：

等　　级
排　　名	269
经　　验	5658
参赛次数	3
文章发表	34
年　　龄	19
在职情况	学生
学　　校	武汉学院
专　　业

　　自我简介：

TA的其他文章

简单易懂，你值得拥有！！！题解1861：程序员爬楼梯（C++代码）
浏览：474

简明易懂，不懂算我输，你值得拥有！(C++代码)
浏览：623

比较简单易上手(C++代码)
浏览：1205

你可能喜欢

【求帮助】C语言程序设计教程（第三版）课后习题8.9 （C语言代码）

【绝对值排序】（C++代码）（利用两个库函数——abs()求绝对值和 sort()快排）

马拦过河卒-题解(C++代码)加油吧！追梦人！

　　作者: KeyWolf　　　　发表时间：2019-12-04 09:24:51 浏览：404　|　评论：0　

原题链接：马拦过河卒

/*********************************************
    分析：
    ①这道题的状态是当前节点，
    ②最优化值是从（0,0）出发到当前节点的路径总数
    ③边界条件为（0,0）点到本身的方案数为1（最小子问题）
    ④第一列，第一行的点的方案数都为1（因为只能往右和往下走），
    ⑤状态转移：因为只能往右走和往下走，
    所以当前节点的方案数是由其左边的节点和上面的节点转移而来，
    所以当前节点的方案数就等于左边节点的方案数加上面节点的方案数
    所以我们就得到了状态转移方程，
    ⑥dp[i][j]=dp[i-1][j]+dp[i][j-1];
    如果是马控制的区域那么那个点的dp值为0。
    ***********************************************/
    #include<bits/stdc++.h>
    using namespace std;
    int dp[20][20];
    bool vis[20][20];//记录为不可达到点 
    int dx[8]={-2,-2,-1,-1,1,1,2,2};//此两行代码为 计算马的控制点 
    int dy[8]={-1,1,-2,2,-2,2,-1,1};
    int main()
    {
    	int x,y,n,m;
    	cin>>n>>m>>x>>y;
    	n++,m++,x++,y++;
    	//重构DP数组，因为第一行的都为权值都为1 如果从第零行开始，
    	//那么根据动态转移方程计算，下标值会变成负数，所以相当于起点（0,0）重构为（1,1) 
    	vis[x][y]=1;
    	dp[1][1]=1;//起点始终为1 
    	vis[1][1]=1;
    	for(int i=0;i<8;i++)//计算马的控制点，并标记在VIS数组中 
    	{
    		int tx,ty;
    		tx=x+dx[i];
    		ty=y+dy[i];
    		if(tx>0&&ty>0&&tx<=n&&ty<=m)
    		vis[tx][ty]=1;
    	}
    	for(int i=1;i<=n;i++)//遍历数组，根据动态转移方程，递推获得答案 
    	{
    		for(int j=1;j<=m;j++)
    		{
    			if(vis[i][j])continue;
    			else
    			{
    				dp[i][j]=dp[i-1][j]+dp[i][j-1];
    				//读者如果还是不明白，可以画图验证一下 
    			}
    		}
    	}
    	cout<<dp[n][m]<<endl;
    	return 0;
    } 
    
    
    /*************************************************************************/
    //天赋决定了你的上限
    //努力决定了你的下限
    //毅力决定了你能在这条路走多远
    //加油吧！编程路上的追梦者！-----------------------------------------------Wolf

0.0分

2 人评分

C语言网推出会员服务，提供C/C++/算法/Python等多套视频学练课程+源码资源社群答疑+私活推荐等资源，享受丰富的技术学习到变现的乐趣，以含金量和学习效果勇敢挑战同类辅导！点击了解开通

KeyWolf

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题7.3 （C语言代码）

【计算球体积】（C语言代码）

printf基础练习2 （C语言代码）

【求帮助】C语言程序设计教程（第三版）课后习题8.9 （C语言代码）

【绝对值排序】（C++代码）（利用两个库函数——abs()求绝对值和 sort()快排）

马拦过河卒-题解(C++代码)加油吧！追梦人！

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题11.3 （C语言代码）

C语言程序设计教程（第三版）课后习题8.3 （Java代码）

用筛法求之N内的素数。（C语言代码）

C语言程序设计教程（第三版）课后习题6.9 （C语言代码）

C语言程序设计教程（第三版）课后习题8.4 （C语言代码）

Minesweeper （C语言描述，蓝桥杯）

有关字符，字符串的输入输出函数说明

星期判断机（C语言代码）

printf基础练习2 （C语言代码）

钟神赛车（C语言代码）

KeyWolf

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题7.3 （C语言代码）

【计算球体积】 （C语言代码）

printf基础练习2 （C语言代码）

【求帮助】C语言程序设计教程（第三版）课后习题8.9 （C语言代码）

【绝对值排序】 （C++代码）（利用两个库函数——abs()求绝对值 和 sort()快排）

马拦过河卒-题解(C++代码)加油吧！追梦人！

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题11.3 （C语言代码）

C语言程序设计教程（第三版）课后习题8.3 （Java代码）

用筛法求之N内的素数。 （C语言代码）

C语言程序设计教程（第三版）课后习题6.9 （C语言代码）

C语言程序设计教程（第三版）课后习题8.4 （C语言代码）

Minesweeper （C语言描述，蓝桥杯）

有关字符，字符串的输入输出函数说明

星期判断机 （C语言代码）

printf基础练习2 （C语言代码）

钟神赛车 （C语言代码）

【计算球体积】（C语言代码）

【绝对值排序】（C++代码）（利用两个库函数——abs()求绝对值和 sort()快排）

　　评论区

用筛法求之N内的素数。（C语言代码）

星期判断机（C语言代码）

钟神赛车（C语言代码）