暑假第11次课 过河卒

课前测：

重点：
数塔问题中，如果自上而下推导，目标是什么？
答： max{f[n][i]}, i∈[1,n];
笔记：

递推（过河卒）

f[i][j]表示从起点到点（i，j）的方案总数
f[i][j]=f[i-1][j]+f[i][j-1];(如果（i，j)是马🐎的控制点，那么f[i][j]=0)
边界：f[1][1]=1;
解：f[m][n]

代码

4391:

#include<iostream>
#include<map>
typedef unsigned long long ull;
using namespace std;
int n,cnt,m,x,y;
map<int,map<int,int> >ma,f;
int main(){
	cin>>n>>m>>x>>y;
//	swap(x,y);
	ma[x+2][y+1]=1;
	ma[x+1][y+2]=1;
	ma[x-1][y+2]=1;
	ma[x-2][y+1]=1;
	ma[x+2][y-1]=1;
	ma[x+1][y-2]=1;
	ma[x-1][y-2]=1;
	ma[x-2][y-1]=1;
	ma[x][y]=1;
	f[0][0]=1;
	for(int i=0;i<=n;i++){
		for(int j=0;j<=m;j++){
			if(i==0&&j==0) continue;
			if(i==0) f[i][j]=f[i][j-1];
			else if(j==0) f[i][j]=f[i-1][j];
			else f[i][j]=f[i-1][j]+f[i][j-1];
			f[i][j]*=(ma[i][j]==0);
		}
	}
	cout<<f[n][m];
}

老师的方法：
定义一个方向数组，表示马走的方向，其他都一样

#include<iostream>
typedef unsigned long long ull;
using namespace std;
int n,cnt,m,x,y;
bool b[50][50];
const int dir[8][2]={
	{-1,-2},{-1,2},{1,-2},{1,2},
	{2,-1},{2,1},{-2,-1},{-2,1}
};
int f[100][100];
int main(){
	cin>>n>>m>>x>>y;
	b[x][y]=1;
	for(int i=0;i<8;i++){
		int nx=x+dir[i][0],ny=y+dir[i][1];
		if(nx>=0&&ny>=0) b[nx][ny]=1;
	} 
	f[0][0]=1;
	for(int i=0;i<=n;i++){
		for(int j=0;j<=m;j++){
			if(i==0&&j==0||b[i][j]) continue;
			if(i-1>=0) f[i][j]=f[i-1][j];
			if(j-1>=0) f[i][j]+=f[i][j-1]; 
		}
	}
//	if(b[0][0]) cout<<0;
	cout<<f[n][m];
}

5100:

f[i][j]表示从起点跳到点(i,j)的方案总数
f[i][j]=f[i-2][j-1]+f[i-1]j-2
边界：f[0][0]=1
解：f[n][m]

代码：

#include<iostream>
#include<map>
typedef unsigned long long ull;
using namespace std;
int n,cnt,m,x,y;
map<ull , map<ull,ull> >f,ju;
int main(){
	cin>>n>>m>>x>>y;
	f[0][0]=1;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			if(i!=x&&j!=y) f[i][j]=f[i-2][j-1]+f[i-1][j-2];
		} 
	}
	cout<<f[n][m];
}

课后测：

重点：注意dir数组