题解【P1002过河卒】
Mr_WA
2019-10-12 13:36:29
大家吼啊——我这个蓝名小蒟蒻又双叒叕来写题解啦!
这道题其实很简单,分成两段写程序就可以啦。但是要注意一个细节,就是枚举马的控制点时,有可能会出现负数,然后我这个蒟蒻非常怂负数,于是我整体向右下挪动了一步。
众所周知,到达一个点的方法数就是到达它的上方格子和左边格子的方法数加起来。用程序来实现,也是非常~~不~~简单的。如下,用递推来实现,也就是程序的第一段了。
```c
for(int i=1; i<=x+1; i++)
{
for(int j=1; j<=y+1; j++)
{
a[i][j]=a[i-1][j]+a[i][j-1];
}
}
cout<<a[x+1][y+1];
```
以上是假设没有马的情况,但是被马控制的格子是不能去的,怎么办呢?
我们需要枚举马的控制点。学过象棋的大佬们都知道,马的控制点最多只有八个,因此可以直接把八个点全部枚举出来,如下:
```c
void bj(int mmx,int mmy)
{
map[mmx][mmy]=1;
map[mmx-1][mmy-2]=1;
map[mmx-2][mmy-1]=1;
map[mmx-2][mmy+1]=1;
map[mmx-1][mmy+2]=1;
map[mmx+1][mmy-2]=1;
map[mmx+2][mmy-1]=1;
map[mmx+2][mmy+1]=1;
map[mmx+1][mmy+2]=1;
}
```
这些被控制的格子全部被标记为1了,这样就好办了,在第一段程序中的for循环中插入这一句话:if(map[i-1][j-1])a[i][j]=0;
如此如此,这般这般,就把程序最重要的两段写出来了。接下来补上文件头、输入什么的小窟窿,并输入return 0二字,就万事大吉啦!
献上既不整齐又不美观的小破代码:
```c
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
unsigned long long x,y,mx,my;
long long a[25][25],map[25][25];//map数组是用来标记的数组
using namespace std;
void bj(int mmx,int mmy)
{
map[mmx][mmy]=1;
map[mmx-1][mmy-2]=1;
map[mmx-2][mmy-1]=1;
map[mmx-2][mmy+1]=1;
map[mmx-1][mmy+2]=1;
map[mmx+1][mmy-2]=1;
map[mmx+2][mmy-1]=1;
map[mmx+2][mmy+1]=1;
map[mmx+1][mmy+2]=1;
}//枚举,标记被马控制的格子
int main()
{
a[1][0]=1;
cin>>x>>y>>mx>>my;//输入不解释
bj(mx,my);//调用标记函数,其实也可以不用函数
for(int i=1; i<=x+1; i++)
{
for(int j=1; j<=y+1; j++)
{
a[i][j]=a[i-1][j]+a[i][j-1];
if(map[i-1][j-1])a[i][j]=0;
}
}//把每一个格子都用上方格子+左边格子的公式算出来,被马控制则为0
cout<<a[x+1][y+1];//输出不解释
return 0;
}
```
全剧终......