2 过河卒[NOIP2002 普及组]

2 过河卒[NOIP2002 普及组] 题目描述

棋盘上A点有一个过河卒，需要走到目标B点。卒行走的规则：可以向下、或者向右。同时在棋盘上C点有一个对方的马，该马所在的点和所有跳跃一步可达的点称为对方马的控制点。因此称之为“马拦过河卒”。

棋盘用坐标表示，A点 (0,0)、B点 (n, m)，同样马的位置坐标是需要给出的。

现在要求你计算出卒从A点能够到达B点的路径的条数，假设马的位置是固定不动的，并不是卒走一步马走一步。

输入格式

一行四个正整数，分别表示B点坐标和马的坐标。

输出格式

一个整数，表示所有的路径条数。

样例输入

6 6 3 3

样例输出

6

题目分析

先简化问题，若没有马，从左上角走到右下角一共有多少种走法？

如果想走到点(n,m)，必须要先走到点(n-1,m)或点(n,m-1)，然后走到点(n,m)；那么求走到点(n,m)的路径条数，就转化为求走到点(n-1,m)的路径条数加上走到点(n,m-1)的路径条数。

假设走到点(n,m)的路径条数是f[n][m]，运用递推思想，若求走到点(5,5)的路径条数，则f[5][5]=f[4][5]+f[5][4]，f[4][5]=f[3][5]+f[4][4]，f[5][4]=f[4][4]+f[5][3]......归纳得f[n][m]=f[n-1][m]+f[n][m-1]。

马的控制点无法走，需要去掉马的控制点上的路径。注意：坐标轴上的点要另行讨论。

代码

#include 
#define N 22
using namespace std;
long long f[N][N]={0};
int a[N][N],n,m,hx,hy;
int b[9][2]={{0,0},{1,2},{2,1},{-1,2},{-2,1},
                   {1,-2},{2,-1},{-1,-2},{-2,-1}};//马的控制范围相对于马位置的偏移量
int main()
{ int x,y,i,j;
  cin>>n>>m>>hx>>hy;
  for(i=0;i<9;i++)
  { x=hx+b[i][0];
    y=hy+b[i][1];//在棋盘上找出马的控制点
    if(x>=0&&x<=n&&y>=0&&y<=m) a[x][y]=1;//判断是否在棋盘范围内，且标记马的控制点
  }
  f[0][0]=1-a[0][0];//若原点为马的控制点，则初始路径数量为0，否则为1
  for(i=0;i<=n;i++)
    for(j=0;j<=m;j++)
  { if(a[i][j]) continue;//马的控制点跳过
    if(i==0&&j==0) continue;
    if(i==0) f[i][j]=f[i][j-1];
    else if(j==0) f[i][j]=f[i-1][j];
    else f[i][j]=f[i-1][j]+f[i][j-1];//运用递推思想
  }
  cout<					
										


					

						
欢迎分享，转载请注明来源：内存溢出
原文地址: http://outofmemory.cn/zaji/5718875.html