算法1

老dfs了，但是会超时（呜呜呜，爆搜出不了奇迹了）

C++ 代码

#include<iostream>
#include<cstring>
using namespace std;

const int N=40;
int vis[N][N];
int dx[2]={1,0},dy[2]={0,1};
int n,m,ans=0;

void dfs(int x,int y)
{
    if(x==n && y==m)
    {
        ans++;
        return ;
    }

    for(int i=0;i<2;i++)
    {
        int xx=x+dx[i];
        int yy=y+dy[i];
        if(vis[xx][yy]==0  && xx<=n && yy<=m)
        {
            vis[xx][yy]=1;
            dfs(xx,yy);
            vis[xx][yy]=0;
        }
    }
}

int main()
{
    scanf("%d%d",&n,&m);
    memset(vis,0,sizeof(vis));
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            if(i%2==0 && j%2==0) vis[i][j]=1;
        }
    }

    dfs(1,1);

    cout<<ans;

    return 0;
}

算法2

老dp了

C++ 代码

#include <iostream>
using namespace std;

const int N = 50;

int f[N][N];

int main()
{
    int n, m;
    cin >> n >> m;

    for (int i = 1; i <= n; i ++)
        for (int j = 1; j <= m; j ++)
        {
            if(i % 2 == 0 && j % 2 == 0) continue;

            if(i == 1 && j == 1) f[i][j] = 1;  //起点到起点            
            else if(i == 1) f[i][j] = 1;       //从左到右            
            else if(j == 1) f[i][j] = 1;       //从上到下           
            else f[i][j] = f[i][j - 1] + f[i - 1][j];     //&& 
        }

    cout << f[n][m] << endl;
    return 0;
}