过河卒问题

发表于 | 更新于: | 分类于 | 阅读次数: |
字数统计: 1.1k 字 | 阅读时长 ≈ 5 分钟

学长给我安利洛谷平台，我打算开始做题然后提升，结果我做过河卒这个题就做了一天。刚开始写的程序有一些逻辑上的漏洞，测试时不能全部通过，曹老板告诉我可以下载测试数据来看，然后就找到漏洞所在，再一个一个的完善，做出来后还是很开心的。
过河卒问题
过河卒问题

我的心路历程

首先可以发现到达当前坐标的路径数等于左边和上边路径数之和，然后我就想构造二维数组，用遍历的方法，把每一个坐标都算出来。在此之前，我需要把第0行第0列赋值为1，也需要判断马控制的坐标(马走日)在不在数组内，并赋值为0，在循环的时候写判断跳过控制点即可。
我的方法就是这么复杂，以至于我刚开始漏掉好多判断条件，比如说当马控制点落在第0行或第0列时，控制点之后都将为0。
当我看题解的时候，发现一堆我看不懂的名词，什么动态规划dp，什么滚动数组，还有用递归的方法做。我这个渣渣还是遍历就好了，等我再学一段时间，再来看会不会这些方法，并写进来。

我的代码

先附上我的遍历方法，学会更好的方法再补充。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
#include <stdio.h>
long long a[21][21];
int define_horse_control1(long long array[21][21],int x,int y)//定义一个函数，把马控制的点赋为0
{
	array[x][y]=0;
	if(x-2>=0&&y-1>=0)array[x-2][y-1]=0;//这里都要判断一下有没有越界 
	if(x-2>=0&&y+1<=20)array[x-2][y+1]=0;
	if(x-1>=0&&y-2>=0)array[x-1][y-2]=0;
	if(x+1<=20&&y-2>=0)array[x+1][y-2]=0;
	if(x+2<=20&&y-1>=0)array[x+2][y-1]=0;
	if(y+1<=20&&x+2<=20)array[x+2][y+1]=0;
	if(x-1>=0&&y+2<=20)array[x-1][y+2]=0;
	if(x+1<=20&&y+2<=20)array[x+1][y+2]=0;
	
	return array[21][21];	
}
int define_horse_control2(long long array[21][21],int x,int y,int n,int m)//如果马的控制点在第0行或者第0列，在马控制点以后的值全为0
{
	if(x-2==0) 
	{
		if(y-1>=1)
		{
			for(int i=y-1;i<=n;i++)a[0][i]=0;
		}else {for(int i=y+1;i<=n;i++)a[0][i]=0;}
	}
	if(x-1==0)
	{
		if(y-2>=1)
		{
			for(int i=y-2;i<=n;i++)a[0][i]=0;
		}else{for(int i=y+2;i<=n;i++)a[0][i]=0;}	
	}
	if(x==0)
	{
		for(int i=y;i<=n;i++)a[0][i]=0;
	}
	if(y-1==0)
	{
		if(x-2>=1)
		{
			for(int i=x-2;i<=m;i++)a[i][0]=0;
		}else{for(int i=x+2;i<=m;i++)a[i][0]=0;}
		
	}
	if(y-2==0)
	{
		if(x-1>=1)
		{
			for(int i=x-1;i<=m;i++)a[i][0]=0;
		}else{for(int i=x+1;i<=m;i++)a[i][0]=0;}
		
	}
	if(y==0)
	{
		for(int i=x;i<=m;i++)a[i][0]=0;
	}
}
int main()
{
	int m,n,x,y;
	scanf("%d %d %d %d",&m,&n,&x,&y);
	a[0][0]=0;
	for(int i=1;i<=n;i++)a[0][i]=1;//到达第一行第一列的点都只有一条路径，都赋值为1
	for(int i=1;i<=m;i++)a[i][0]=1;//到达第一行第一列的点都只有一条路径，都赋值为1
	define_horse_control1(a,x,y);//把马控制的点赋为0
	define_horse_control2(a,x,y,n,m);//如果马的控制点在第0行或者第0列，在马控制点以后的值全为0
	
	for(int i=1;i<=m;i++)//遍历计算到当前坐标的路径数，只需要遍历到第m行和第n列即可。 
	{
		for(int j=1;j<=n;j++)
		{
			if((i==x-2&&j==y-1)||(i==x-2&&j==y+1)||(i==x-1&&j==y-2)||(i==x+1&&j==y-2)||(i==x+2&&j==y-1)||(j==y+1&&i==x+2)||(i==x-1&&j==y+2)||(i==x+1&&j==y+2)||(i==x&&j==y))
			{
				continue;//跳过马的控制点的计算 
			}
			a[i][j]=a[i][j-1]+a[i-1][j];//当前坐标的路径数等于左边和上边路径数之和
		}
	}

	printf("%lld",a[m][n]);
	return 0;
}