2067. 走方格

2067. 走方格 - AcWing题库

第一眼就是暴搜2333
结果显而易见，卡数据了，9/10，最后一个过不了
DFS:

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 35;
int n,m;
int cnt;
void dfs(int x,int y)
{
    if(x>n || y>m)return;
    if(x % 2 == 0 && y % 2 ==0) return;
    if(x==n && y==m)
    {
        cnt++;
        return;
    }
    dfs(x+1,y),dfs(x,y+1);
    
}
int main()
{
    cin >> n >> m;
    dfs(1,1);
    cout << cnt << endl;
}

BFS:

#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
#define x first
#define y second
using namespace std;
typedef pair<int,int> PII;
const int N = 35;
int n,m;
int cnt;
int dx[2]={0,1},dy[2]={1,0};
void bfs(int x,int y)
{
    queue<PII>q;
    q.push({x,y});
    while(q.size())
    {
        PII t = q.front();
        q.pop();
        for(int i=0;i<2;i++)
        {
            int x = t.x+dx[i],y=t.y+dy[i];
            if(x>n || y>m)continue;
            if(x % 2 == 0 && y % 2 ==0)continue;
            if(x==n && y==m)
            { 
                cnt++;
            }
            q.push({x,y});
        }
    }
}
int main()
{
    cin >> n >> m;
    bfs(1,1);
    cout << cnt << endl;
}

那么就要转变思路了，显然暴搜可以优化成dp

#include<iostream>
#include<algorithm>
using namespace std;
const int N =35;
int dp[N][N];
int n,m;

int main()
{
	cin >> n >> m;
	dp[1][1]=1;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
		    if(i%2!=0 || j%2!=0)
			    dp[i][j]+=dp[i-1][j]+dp[i][j-1];
	cout << dp[n][m] << endl;
	return 0;
}