STUDY|算法设计

• 递推等
• • 小明贴地板
  • 过河卒

分析1
分析2

f[i][j]=max⁡(f[i−1][j]+f[i][j−1],f[i][j])

#include  
#define N 99
using namespace std;
int dx[8]={-2,-1,1,2,2,1,-1,-2};
int dy[8]={-1,-2,-2,-1,1,2,2,1};//左上角开始逆时针 

int main(){
	int n,m,x,y;
	bool flag[N][N]={};//标记是否可达数组 
	int a[N][N]={};
	cin>>n>>m>>x>>y;
	//将不可达位置 置1 马(x,y) 
	flag[x][y]=1;
	for(int i=0;i<8;i++){
		if(x+dx[i]>=0&&y+dy[i]>=0)
			flag[x+dx[i]][y+dy[i]]=1;
	}
		
	//路径数计算 
	a[0][0]=1;
	for(int i=0 ;i<=n;i++)
		for(int j=0;j<=m;j++){
			if(flag[i][j]==0){
				a[i][j]=max(a[i-1][j]+a[i][j-1],a[i][j]);
				//a[i][j]=a[i-1][j]+a[i][j-1];
			}
		} 		
	cout<