刘嘉柚 • 4个月前
这题其实是奥数的标数法的改版,每个点的走法数就是左边点的走法数加上面点的走法数。 即可推出递推式:
a[i][j] = a[i-1][j] + a[i][j-1];
然后只需要判断走到的点不能被马走到就行了。
#include<bits/stdc++.h>
using namespace std;
bool h[25][25];
long long a[25][25]; //dp数组
int main()
{
a[1][1]=1;
int n,m,x,y;
cin>>n>>m>>x>>y;
n += 1; m += 1; x += 1; y += 1;
h[x][y] = 1;//枚举标记马的位置
h[x+1][y+2] = 1;
h[x-1][y+2] = 1;
h[x+1][y-2] = 1;
h[x-1][y-2] = 1;
h[x+2][y+1] = 1;
h[x+2][y-1] = 1;
h[x-2][y+1] = 1;
h[x-2][y-1] = 1;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++) {
if((i!=1||j!=1)&&!h[i][j]) //判断走的点不能被马走到
a[i][j]=a[i-1][j]+a[i][j-1]; //递推式
}
cout<<a[n][m];
return 0;
}
评论: