递推2--过河卒(Noip2002)
2024-10-15 19:35:45
递推2--过河卒(Noip2002)
一、心得
写出递推公式就OK了,具体编程还是很简单的
二、题目及分析
过河卒(NOIp2002)
【问题描述】
棋盘上A点有一个过河卒,需要走到目标B点。卒行走的规则:可以向下、或者向右。同时在棋盘上C点有一个对方的马,该马所在的点和所有跳跃一步可达的点称为对方马的控制点。因此称之为“马拦过河卒”。
棋盘用坐标表示,A点(0, 0)、B点(n, m),(n, m为不超过20的整数),同样马的位置坐标是需要给出的。C≠A且C≠B。现在要求你计算出卒从A点能够到达B点的路径的条数,假设马的位置是固定不动的,并不是卒走一步马走一步。
三、代码及结果
这里取起点:A(0,0) 终点:B(4,8) 马的位置:C(2,4)
/*
过河卒问题
f[r][c]表示到达(r,c)位置的路径条数
只能从上面来或者从左边来
f[r][c]=从上面一行来+从左边一列来
f[r][c]=f[r-1][c]+f[r][c-1]
如果这点被马控制,那么:
f[r][c]=0;
所以从上往下,从左往右依次递推就好了
那些边界都为0,且f[0][0]=1
*/
#include <iostream>
#define Max 25
using namespace std;
//r在前c在后
int horseControl[][]={{,},{-,},{-,},{,},{,},{,-},{,-},{-,-},{-,-}};
int dp[Max][Max];//f[r][c]表示到达(r,c)位置的路径条数
int horse[Max][Max];//判断该点是否被马控制 // 初始化马的控制点
void initHorseControl(int r,int c){//马的坐标需要被传进来
horse[Max][Max]={};//对house初始化为0
for(int i=;i<;i++){
int r1=r+horseControl[i][];
int c1=c+horseControl[i][];
if(r1>=&&c1>=){
horse[r1][c1]=;
}
}
} //显示数组中的内容
void showArray(int x,int y,int a[Max][Max]){
for(int i=;i<=x;i++){
for(int j=;j<=y;j++){
printf("%5d ",a[i][j]);
}
printf("\n");
}
} // 初始化棋盘
void initChessboard(int r,int c){
for(int i=;i<=r;i++){//对列进行初始化
dp[i][]=;
}
for(int j=;j<=c;j++){
dp[][j]=;
}
dp[][]=;
} //递推操作
void dpOperation(int r,int c){
for(int i=;i<=r;i++){
for(int j=;j<=c;j++){
if(horse[i][j]==){//表示被马控制
dp[i][j]=;
}
else{
dp[i][j]=dp[i-][j]+dp[i][j-];
}
}
}
} int main(){
//是要算题中4,8的,但是我们存储的是线,有行5条,列9条
//
int r=,c=;//格子行和列,也就是目的点的坐标
int x=,y=;//马所在的点
cout<<"起点:A(0,0) 终点:B(4,8) 马的位置:C(2,4)"<<endl;
initHorseControl(x,y);// 初始化马的控制点
cout<<"---------------------------------------------------------------------"<<endl;
cout<<"马控制的点:"<<endl;
showArray(r,c,horse);
cout<<"---------------------------------------------------------------------"<<endl;
initChessboard(r,c);// 初始化棋盘
cout<<"初始化的棋盘:"<<endl;
showArray(r,c,dp);
cout<<"---------------------------------------------------------------------"<<endl;
dpOperation(r,c);//递推操作
cout<<"进行了路径计算后的棋盘:"<<endl;
showArray(r,c,dp);
cout<<"---------------------------------------------------------------------"<<endl;
cout<<"A点到B点的路径条数是:"<<dp[r][c]<<endl;
return ;
}
最新文章
- Javaweb——过滤器映射
- sql server pivot/unpivot 行列互转
- js location对象
- MVC WebAPI 三层分布式框架开发
- codevs 2491 玉蟾宫
- LaTex学习笔记(一):review
- codeforces 484B B. Maximum Value(二分)
- Android优化——UI检视利器:Hierarchy Viewer
- Project Euler 97 :Large non-Mersenne prime 非梅森大素数
- p
- 基于cygwin构建u-boot(二)gcc的C语言标准版本号(-std=)
- QT:浮动的饼状统计图(自绘不规则窗口)
- SqlCacheDependency的使用
- linux下载时提示请尝试移除磁盘中不需要的文件并重试,或者保存到其他位置
- redis 报Operation against a key holding the wrong kind of value警告的解决方法
- [bzoj4592] [Shoi2015]脑洞治疗仪
- Python HTTP库requests中文页面乱码解决方案!
- java 数字左补齐0
- Spring SpringMVC SpringBoot SpringCloud概念、关系及区别
- ngnix和负载均衡