洛谷p1002(过河卒)

题目描述 

如图，A 点有一个过河卒，需要走到目标 B 点。卒行走规则：可以向下、或者向右。同时在棋盘上的任一点有一个对方的马（如上图的C点），该马所在的点和所有跳跃一步可达的点称为对方马的控制点。例如下图 C 点上的马可以控制 9 个点（图中的P1，P2 … P8 和 C）。卒不能通过对方马的控制点。

棋盘用坐标表示，A 点（0，0）、B 点（n,m）(n,m 为不超过 20 的整数，并由键盘输入)，同样马的位置坐标是需要给出的。现在要求你计算出卒从 A 点能够到达 B 点的路径的条数。

输入

键盘输入
B点的坐标（n,m）以及对方马的坐标（X,Y）

输出

屏幕输出
一个整数（路径的条数）。

题目分析

一、模拟棋盘用一个二维数组

二、设计移动路线算法

1.dfs

可以想到dfs,直接深搜，采用递归的方法来写（不过运行时间不够用）

就直接给出代码看一下好了，应该答案是不会有问题的

#include <stdio.h>

int count=0;
int m_x[2]={0,1};
int m_y[2]={1,0};
static int a[25][25];
void f(int n,int m,int x,int y){
	int i;
	if(n==x&&m==y)
	count++;
	else
	for(i=0;i<=1;i++){
		if(a[n+m_x[i]][m+m_y[i]]==0&&n+m_x[i]<=x&&m+m_y[i]<=y){
			a[n+m_x[i]][m+m_y[i]]==1;
			f(n+m_x[i],m+m_y[i],x,y);
			a[n+m_x[i]][m+m_y[i]]==0;
		}
	}
}

int main(){
	int n,m,x,y;
	scanf("%d%d%d%d",&n,&m,&x,&y);
    a[x][y]=1;
	a[x+2][y+1]=1;
	a[x+1][y+2]=1;
	a[x-1][y+2]=1;
	a[x-2][y+1]=1;
	a[x-2][y-1]=1;
	a[x-1][y-2]=1;
	a[x+1][y-2]=1;
	a[x+2][y-1]=1;
	f(0,0,n,m);
	printf("%d",count);
	
	return 0;
}

2.直接递推 

递推怎么个推法呢，很显然可以用到这样一个数学知识，计数原理

高中学过分类加法和分步乘法

这里用什么呢，我选择做加法，为什么呢

因为其实仔细想想，卒的走法也就两种向左或向下

先看代码吧

for(i=0;i<=n;i++){
    	for(j=0;j<=m;j++){
    		if(i!=0||j!=0)
    		if(a[i][j]!=0){
    		if(i>0&&j>0)
    		a[i][j]=a[i][j-1]+a[i-1][j];
    		else if(i==0)
    		a[i][j]=a[i][j-1];
			else
			a[i][j]=a[i-1][j];
			}
		}
	}

棋盘上的每一个点都有两条到的路线从左或从上，这就是关键

细节问题（可以先看下面的代码）

看这个之前可以先看看下面的代码，这里是说一下赋值的问题，我之所以那样赋值其实是由我的核心算法决定的，那个赋值为1没必要全赋值是1，主要是赋值0，控制点不能过要相应减少一种路径，由于是加法加0即好

完整代码 

#include <stdio.h>

static long long int a[25][25];        //模拟棋盘
int main(){
	int n,m,x,y;
	scanf("%d%d%d%d",&n,&m,&x,&y);
	int i,j;
	for(i=0;i<=n;i++){                //初始化
    	for(j=0;j<=m;j++){
    		a[i][j]=1;                //这次的1有讲究，下面的0也是
    	}
    }
    a[x][y]=0;
	a[x+2][y+1]=0;
	a[x+1][y+2]=0;
	if(x-1>=0)                      //是否不在棋盘内
	a[x-1][y+2]=0;
	if(x-2>=0)
	a[x-2][y+1]=0;
	if(x-2>=0&&y-1>=0)
	a[x-2][y-1]=0;
	if(x-1>=0&&y-2>=0)
	a[x-1][y-2]=0;
	if(y-2>=0)
	a[x+1][y-2]=0;
	if(y-1>=0)
	a[x+2][y-1]=0;

    for(i=0;i<=n;i++){             //核心算法
    	for(j=0;j<=m;j++){
    		if(i!=0||j!=0)
    		if(a[i][j]!=0){
    		if(i>0&&j>0)
    		a[i][j]=a[i][j-1]+a[i-1][j];
    		else if(i==0)
    		a[i][j]=a[i][j-1];
			else
			a[i][j]=a[i-1][j];
			}
		}
	}
	printf("%lld",a[n][m]);
	
	return 0;
}