【题解】【递推】—— [NOIP2002 普及组] 过河卒
- [NOIP2002 普及组] 过河卒
- 题目描述
- 输入格式
- 输出格式
- 输入输出样例
- 输入 #1
- 输出 #1
- 提示
- 1.题意解析
- 2.AC代码
[NOIP2002 普及组] 过河卒
戳我查看题目(洛谷)
题目描述
棋盘上 A A A 点有一个过河卒,需要走到目标 B B B 点。卒行走的规则:可以向下、或者向右。同时在棋盘上 C C C 点有一个对方的马,该马所在的点和所有跳跃一步可达的点称为对方马的控制点。因此称之为“马拦过河卒”。
棋盘用坐标表示, A A A 点 ( 0 , 0 ) (0, 0) (0,0)、 B B B 点 ( n , m ) (n, m) (n,m),同样马的位置坐标是需要给出的。
现在要求你计算出卒从 A A A 点能够到达 B B B 点的路径的条数,假设马的位置是固定不动的,并不是卒走一步马走一步。
输入格式
一行四个正整数,分别表示 B B B 点坐标和马的坐标。
输出格式
一个整数,表示所有的路径条数。
输入输出样例
输入 #1
6 6 3 3
输出 #1
6
提示
对于 100 % 100 \% 100% 的数据, 1 ≤ n , m ≤ 20 1 \le n, m \le 20 1≤n,m≤20, 0 ≤ 0 \le 0≤ 马的坐标 ≤ 20 \le 20 ≤20。
【题目来源】
NOIP 2002 普及组第四题
1.题意解析
这是一道很经典的动态规划 递推的题目。
先假设没有那个碍事的马。
通过观察可以发现,每个点都可以通过它上面的点或左边的点到达。即点f[i][j]
能通过点f[i-1][j]
和点f[i][j-1]
到达。则递推公式为:
a[i][j]=a[i-1][j]+a[i][j-1];
如果是在 x x x轴上或 y y y轴上,那么只有一种方法能到达(一路走到底)。所以递推边界是f[0][i]=f[i][0]=1
。
那么接下来就是处理马的控制点了。先定义一个数组dx[][2]
,储存每个马的控制点对于马所在点的偏移量。得到马的坐标(x,y)
之后就使用循环加上dx
偏移量,计算马的控制点。再定义一个数组ctrl
,储存点(i,j)
是不是马的控制点。
如果有些点因为马的把守而无法从马的控制点转移到下一个点,那么就不进行转移。
注意:如果马的控制点刚好落在起点(0,0)
上,哪么马就不能走了。所以初始条件要改成f[0][0]=1-ctrl[0][0];
,递推式要改成:
if(i!=0)f[i][j]+=f[i-1][j];//没有在纵坐标上
if(j!=0)f[i][j]+=f[i][j-1];//没有在横坐标上
如果一个点(i,j)
是马的控制点(即ctrl[i][j]=1
),直接continue
。否则依此计算每个点可到达的路径数。
2.AC代码
#include<bits/stdc++.h>
using namespace std;
#define MAXN 25
long long f[MAXN][MAXN];//储存整个棋盘
int n,m,hx,hy,ctrl[MAXN][MAXN];//ctrl[i][j]表示(i,j)是否是马的控制点
int d[][2]={{0,0},{2,1},{1,2},{-1,2},{-2,1},{-2,-1},{-1,-2},{1,-2},{2,-1}};
//表示马的每个控制点对于它本身的偏移量(包括自己所在的点)
int main()
{cin>>n>>m>>hx>>hy;for(int i=0;i<9;i++)//找到所有马的控制点if(hx+d[i][0]>=0&&hx+d[i][0]<=n&&hy+d[i][1]>=0&&hy+d[i][1]<=m)//判断是否超出边界ctrl[hx+d[i][0]][hy+d[i][1]]=1;//没超出边界这个点就是马的控制点 f[0][0]=1-ctrl[0][0];//如果起点恰好是马的控制点,那就没有任何路可走 for(int i=0;i<=n;i++)//枚举x坐标for(int j=0;j<=m;j++)//枚举y坐标{if(ctrl[i][j])continue;//是马的控制点就不能走 if(i!=0)f[i][j]+=f[i-1][j];//没有在纵坐标上 if(j!=0)f[i][j]+=f[i][j-1];//没有在横坐标上 }cout<<f[n][m];//输出答案 return 0;
}
喜欢就订阅此专辑吧!
【蓝胖子编程教育简介】
蓝胖子编程教育,是一家面向青少年的编程教育平台。平台为全国青少年提供最专业的编程教育服务,包括提供最新最详细的编程相关资讯、最专业的竞赛指导、最合理的课程规划等。本平台利用趣味性和互动性强的教学方式,旨在激发孩子们对编程的兴趣,培养他们的逻辑思维能力和创造力,让孩子们在轻松愉快的氛围中掌握编程知识,为未来科技人才的培养奠定坚实基础。
欢迎扫码关注蓝胖子编程教育