递推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 ;

 }