30pts(dfs)

从右下角往左边搜索，需要满足左下到右上对角线依次递减，如果w[x+1][y-1]=w[x][y],那么以x+1,y为左上角顶点的对角线也相等。

#include<bits/stdc++.h>
using namespace std;
const int N=10;
int n,m;
int w[N][N];
bool st[N][N];
bool check(int x,int y)
{
    if(x<n&&y>1&&w[x+1][y-1]==w[x][y]&&!st[x+1][y]) //
    {
        return false;
    }
    return true;
}
int dfs(int x,int y)
{
    if(!y) return dfs(x-1,m);//上面一行
    if(!x) return 1;//搜索完成
    if(x==n||y==m||w[x+1][y]==w[x][y+1]&&st[x+1][y]&&st[x][y+1])
    {
        st[x][y]=true;
    }
    else
    {
        st[x][y]=false;
    }
    int res=0;
    if(x==n||y==1||w[x+1][y-1]) //可以填1
    {
        w[x][y]=1;
        if(check(x,y)) res+=dfs(x,y-1);
    }
    w[x][y]=0; //填0
    if(check(x,y)) res+=dfs(x,y-1);
    return res;
}
int main()
{
    cin>>n>>m;
    cout<<dfs(n,m);
    return 0;
}

根据搜索结果总结规律。

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=10,MOD=1e9+7;
int g[N][N]={
    {},
    {0, 2, 4, 8, 16, 32, 64, 128, 256, },
    {0, 4, 12, 36, 108, 324, 972, 2916, 8748, },
    {0, 8, 36, 112, 336, 1008, 3024, 9072, 27216, },
    {0, 16, 108, 336, 912, 2688, 8064, 24192, 72576, },
    {0, 32, 324, 1008, 2688, 7136, 21312, 63936, 191808, },
    {0, 64, 972, 3024, 8064, 21312, 56768, 170112, 510336, },
    {0, 128, 2916, 9072, 24192, 63936, 170112, 453504, 1360128, },
    {0, 256, 8748, 27216, 72576, 191808, 510336, 1360128, 3626752, 10879488, },
};
int qmi(int a,int b)
{
    int res=1;
    while(b)
    {
        if(b&1) res=(LL)res*a%MOD;
        a=(LL)a*a%MOD;
        b=b>>1;
    }
    return res;
}
int main()
{
    int n,m;
    cin>>n>>m;
    if(n<=8&&m<=8||n==8&&m==9)
    {
        cout<<g[n][m]<<endl;
    }
    else if(n==1)
    {
        cout<<qmi(2,m)<<endl;
    }
    else
    {
        cout<<(LL)g[n][n+1]*qmi(3,m-n-1)%MOD;
    }
    return 0;
}