题解 2577: 蓝桥杯2020年第十一届省赛真题-走方格

解题思路:利用记忆化递归进行搜索

注意事项:注意将终点dp[n][m]设为1

参考代码:

#pragma GCC optimize(1)
#pragma GCC optimize(2)
#pragma GCC optimize(3,"Ofast","inline")
#include<iostream>
#define None -1
using namespace std;
//记忆化递归
int n,m;//行数列数 
int dp[31][31]={0};//dp[i][j]存储从(i,j)到(n,m)的方式数 
int path(int i,int j){
	if(dp[i][j]!=None) return dp[i][j];
	int right_path=0;//向右走后的方式数 
	int down_path=0;//向下走后的方式数 
	if(!(i%2==0&&(j+1)%2==0)&&j!=m){
		right_path=path(i,j+1);
		//cout<<"right:"<<"("<<i<<","<<j<<")->("<<i<<","<<j+1<<")"<<endl;
	} 
	if(!(j%2==0&&(i+1)%2==0)&&i!=n){
		down_path=path(i+1,j);
		//cout<<"down:"<<"("<<i<<","<<j<<")->("<<i+1<<","<<j<<")"<<endl;
	}
	dp[i][j]=right_path+down_path;
	return dp[i][j];
} 
int main(){
	cin>>n>>m;
	for(int i=1;i<=n;++i){
		for(int j=1;j<=m;++j){
			dp[i][j]=None;
		}
	}
	dp[n][m]=1;
	cout<<path(1,1);
}