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 30long 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;}