过河卒

解题思路

• lan[][]:马会走到的地方
• f[i][j]:能到达i,j点的路数
• 能到达点(i,j)的条数=能到达（i-1,j）的条数+能到达（i,j-1）的条数
• 这题难点在于如何初始化f[][]数组？ 因为马一下跳两格，所以要将数组往右下移两格。可以这样想：数出到某一点有几条路，然后往前推出要初始化的点。

解题代码

#include<bits/stdc++.h>
using namespace std;
const int N=30;
#define ll long long
int main(){
	int n,m,x,y;
	cin>>n>>m>>x>>y;
	n+=2;m+=2;x+=2;y+=2;
	int dir[8][2]={{-1,-2},{-2,-1},{-2,1},{-1,2},{1,2},{2,1},{2,-1},{1,-2}}; 
	bool lan[N][N]={0};//马会走到的地方 
	ll f[N][N]={0};//注意数据会变得很大，所以开ll 
	lan[x][y]=1; 
	for(int i=0;i<8;i++) lan[x+dir[i][0]][y+dir[i][1]]=1; 
	f[2][1]=1;//初始化 
	for(int i=2;i<=n;i++){
		for(int j=2;j<=m;j++){
			if(lan[i][j]) continue;
			f[i][j]=f[i-1][j]+f[i][j-1]; 
		}
	}
	cout<<f[n][m]<<endl;
	return 0;
}