题意分析
- 目标:从A点走到B点
- 基本操作:向右走 和 向下走
- 本题因为起点和终点都是确定的,所以顺推和逆推都是相同的。下文就讲解逆推的分析
- 点(i,j)的方案数等于点(i,j-1)和点(i-1,j)的方案数和
- 限制条件:马所可以攻击到的点不能走
代码实现(对应上述各点)
- 构建数组F[ i ][ j ],用于存储到达坐标点(i,j) 的路径数,起点为F[ 0 ][ 0 ],终点为F[ n ][ m ]
- F[ i ][ j ]=F[ i-1 ][ j ]+F[ i ][ j-1 ]
- 构建bool数组B[ i ][ j ] 用于记录点(i,j)能否到达此点
动态转移方程:F[i][j]=F[i-1][j+F[i][j-1] 边界条件:F[0][j]=1,F[i][0]=1;(0<=i<=Bx,0<=j<=By)
完整代码
#include<algorithm>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<string>
using namespace std;
long long a[25][25];
int main(void)
{
int cx,cy,bx,by;
memset(a,0,sizeof(a));
cin>>bx>>by>>cx>>cy;
for(int i=1; i<=bx+1; ++i)
{
for(int j=1; j<=by+1; j++)
{
a[i][j]=1;
}
}
bx+=1;//位置从(1,1)有助于构建边界
by+=1;
cx+=1;
cy+=1;
a[1][1]=1;
a[cx][cy]=0;//下面标记马所能到达的点
a[cx+2][cy+1]=0;
a[cx-2][cy+1]=0;
a[cx+2][cy-1]=0;
a[cx-2][cy-1]=0;
a[cx+1][cy+2]=0;
a[cx+1][cy-2]=0;
a[cx-1][cy+2]=0;
a[cx-1][cy-2]=0;
for(int i=1; i<=bx; ++i)
{
for(int j=1; j<=by; j++)
{
if(i==1&&j==1)
{
continue;
}
else
{
if(a[i][j])
{
a[i][j]=a[i-1][j]+a[i][j-1];
}
}
}
}
cout<<a[bx][by]<<endl;
return 0;
}