马拦过河卒(双重循环实现)-洛谷-P1002

P1002 [NOIP2002 普及组] 过河卒

一、题目描述

二、一些关键信息：

1、一个点的来源路径只能是上路径或者左路径。

2、换成字母描述：

一个点是A，A点的做路径来源是B，A点的上路径来源是C

那么A、B和C的坐标分别就是：

f(x,y)、f(x-1,y)、f(x,y-1)

3、可能性描述：

B点从起始点走过来的路径可能性是m,

C点从起始点走过来的路径可能性是n

那么到达A点的可能性只能是m+n

4、利用坐标表示可能性那么得到公式

5、特殊点的可能性：

三、代码编写

1、数据变量准备：

//数量的准备 说明/提示里有最大值的范围，超过最大值就可以
#define SL 30
//B点坐标 马的坐标
int xb = 0,yb = 0,xm = 0,ym = 0;
//棋盘
int qp[SL][SL] = {0};
//每个点对应步数的准备
int bs[SL][SL] = {0};

2、输入B点的坐标和马的坐标

//输入 B点 马的坐标
cin >> xb >> yb >> xm >> ym;

3、整体平移

//整体平移
xb+=2;yb+=2;xm+=2;ym+=2;

4、特殊点赋值

//特殊点 边界和马的坐标
//初始化 C++的二维数组的初始化方式有限，不能直接使用[][]的方式来初始化
for(int i =0;i<SL;i++){
for(int j=0;j<SL;j++){
bs[i][j] = 0;
qp[i][j] = 0;
}
}
//边界
for(int i=2;i<SL;i++){
bs[i][0] = 1;//横线
bs[0][i] = 1;//竖线
}
//马的控制点
qp[xm][ym] = 1;
qp[xm-2][ym-1] = 1;
qp[xm-1][ym-2] = 1;
qp[xm-2][ym+1] = 1;
qp[xm-1][ym+2] = 1;
qp[xm+2][ym+1] = 1;
qp[xm+2][ym-1] = 1;
qp[xm+1][ym-2] = 1;
qp[xm+1][ym+2] = 1;

5、递推计算

//递推计算
bs[1][2] = 1;
for(int i =2;i<=xb;i++){
for(int j=2;j<=yb;j++){
if(qp[i][j] == 0) {
bs[i][j] = bs[i-1][j] + bs[i][j-1];
}
}
}

6、输出打印查看

//打印查看
for(int i =0;i<SL;i++){
for(int j=0;j<SL;j++){
cout << bs[i][j] << " ";
}
cout << endl;
}
//输出
cout << bs[xb][yb] << endl;

最终结果

四、所有代码（通过测评）

#include <bits/stdc++.h>
using namespace std;
#define SL 30
long long xa = 0,ya = 0;
long long xm = 0,ym = 0;
long long qp[SL][SL] = {0};
long long f[SL][SL] = {0};
int main() {
//输入这四个数
cin >> xa >> ya >> xm >> ym;
xa+=2;
ya+=2;
xm+=2;
ym+=2;
for(int i=0;i<SL;i++){
for(int j=0;j<SL;j++){
qp[i][j] = 0;
f[i][j] = 0;
}
}
//特殊点
for(int i=2;i<SL;i++){
f[i][2] = 1;
f[2][i] = 1;
}
qp[xm][ym] = 1;
qp[xm-1][ym+2] = 1;
qp[xm-1][ym-2] = 1;
qp[xm-2][ym+1] = 1;
qp[xm-2][ym-1] = 1;
qp[xm+1][ym+2] = 1;
qp[xm+1][ym-2] = 1;
qp[xm+2][ym+1] = 1;
qp[xm+2][ym-1] = 1;
f[1][2] = 1;
for(int i=2;i<=xa;i++){
for(int j=2;j<=ya;j++){
if(qp[i][j]==0){
f[i][j] = f[i-1][j] + f[i][j-1];
}else{
f[i][j] = 0;
}
}
}
//输出
cout << f[xa][ya] << endl;
return 0;
}