KeyWolf

用户名：17354378026

访问量：18624

签　名：

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

　　自我简介：

TA的其他文章

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

三角形-题解（23行代码解决问题）加油吧！追梦人！
浏览：521

Tom数-题解(C++代码)加油吧，追梦人！
浏览：1139

你可能喜欢

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

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

　　作者: KeyWolf　　　　发表时间：2019-12-04 09:24:51 浏览：556　|　评论：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 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

KeyWolf

TA的其他文章

你可能喜欢

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

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

C二级辅导-进制转换（C语言代码）

分糖果（C++代码）

哥德巴赫曾猜测（C语言代码）

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

评论区

精彩推荐

最长单词（C语言代码）

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

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

三角形（C++代码）递推

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

【计算直线的交点数】（C语言代码）

蚂蚁感冒（C语言代码）

A+B for Input-Output Practice (III) （C语言代码）

C二级辅导-温度转换（C语言代码）

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

KeyWolf

TA的其他文章

你可能喜欢

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

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

C二级辅导-进制转换 （C语言代码）

分糖果 （C++代码）

哥德巴赫曾猜测 （C语言代码）

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

评论区

精彩推荐

最长单词 （C语言代码）

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

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

三角形 （C++代码）递推

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

【计算直线的交点数】 （C语言代码）

蚂蚁感冒 （C语言代码）

A+B for Input-Output Practice (III) （C语言代码）

C二级辅导-温度转换 （C语言代码）

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

C二级辅导-进制转换（C语言代码）

分糖果（C++代码）

哥德巴赫曾猜测（C语言代码）

　　评论区

最长单词（C语言代码）

三角形（C++代码）递推

【计算直线的交点数】（C语言代码）

蚂蚁感冒（C语言代码）

C二级辅导-温度转换（C语言代码）