一列一列枚举填哪个数字(加法原理),再枚举行在哪里断开(乘法原理)。

#include <stdio.h>
#include <string.h>
const int N=45, mo=998244353;
int n, m, i, j, k, f[N][N][N][15];
char s[N][N];
int dfs(int k, int x, int y, int a){
    if(x > y) return 1;//优先级更高:不存在,填10也行
    if(k > m) return x == y;
    if(a > 9) return 0;
    if(~f[k][x][y][a]) return f[k][x][y][a];
    int i, v=dfs(k, x, y, a+1);//第k列至少为a+1的情况
    for(i=x; i<=y; i++){
        if(s[i][k]!='?' && s[i][k]-48!=a) break;
        v = (v + 1ll*dfs(k+1, x, i, 0)*dfs(k, i+1, y, a+1)) % mo;
    }//第k列最小是a的情况:[x, i]填a,[i+1, y]至少a+1
    return f[k][x][y][a] = v;
}//第x~y行,第k列至少为a 
int main(){
    scanf("%d%d", &n, &m);
    for(i=1; i<=n; i++) scanf("%s", s[i]+1);
    memset(f, -1, sizeof(f));
    printf("%d\n", dfs(1, 1, n, 0));
    return 0;
}

作者 crxis

发表回复