天下一プログラマーコンテスト2014予選A C問題 天下一文字列集合

天下一プログラマーコンテスト2015の予選がもうすぐだったので練習がてらやってみました。
C問題以降はどれも難しかったし、解説なかったから辛かったですね…。

文字列に'*'が入った集合がわたされて、それらを全て満たす最小の集合の大きさを求める問題です。
イメージ的にはまとめられるものはまとめて小さくしてしまおう！という感じなのですか、最初貪欲に書いたら嘘解法だったのに部分点来てしまった…。

で解法ですが、ある文字列とある文字列がまとめられるかのtableを作成します。
そして、どれをまとめるかでdpをします。せっかく集合が14個と少ないのでbit_dpでごにょごにょやればできます。

    int N, M; cin >> N >> M;
    string S[N];
    for(int i=0; i<N; i++) cin >> S[i];

    bool table[N][N];
    rep(i, N) rep(j, N){
        bool ok = true;
        for(int k=0; k<M; k++){
            if(S[i][k] != '*' && S[j][k] != '*' && S[i][k] != S[j][k]) ok = false;
        }
        table[i][j] = ok;
    }

    int dp[(1<<N)];
    memset(dp, -1, sizeof(dp));
    dp[0] = 0;
    for(int i=1; i<(1<<N); i++){
        bool ok = true; //まとめられる
        for(int j=0; j<N; j++){
            if((i>>j)&1){
                for(int k=0; k<N; k++){
                    if((i>>k)&1){
                        if(!table[j][k]) ok = false;
                    }
                }
            }
        }
        if(ok){
            for(int j=0; j<(1<<N); j++){
                if((i&j) == 0 && dp[j] != -1 && (j|i)<(1<<N)){
                    if(dp[j|i] == -1) dp[j|i] = dp[j]+1;
                    else dp[j|i] = min(dp[j]+1, dp[j|i]);
                }
            }
        }
    }
    cout << dp[(1<<N)-1] << endl;