Submission #8534290

Source Code Expand

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <bits/stdc++.h>
#define REP(i, n) for (int i = 0; (i) < (int)(n); ++ (i))
#define REP3(i, m, n) for (int i = (m); (i) < (int)(n); ++ (i))
#define REP_R(i, n) for (int i = (int)(n) - 1; (i) >= 0; -- (i))
#define REP3R(i, m, n) for (int i = (int)(n) - 1; (i) >= (int)(m); -- (i))
#define ALL(x) std::begin(x), std::end(x)
using namespace std;
template <class T, class U> inline void chmin(T & a, U const & b) { a = min<T>(a, b); }
int solve(int n, int m, const vector<string> & p) {
    vector<bool> mergeable(1 << n, true);
    REP (s, 1 << n) {
        if (__builtin_popcount(s) <= 1) {
            // nop
        } else if (__builtin_popcount(s) == 2) {
            int a = __builtin_ctz(s);
            int b = __builtin_ctz(s & ~ (1 << a));
            REP (i, m) {
                if (p[a][i] != '*' and p[b][i] != '*' and p[a][i] != p[b][i]) {
                    mergeable[s] = false;
                }
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

#include <bits/stdc++.h>
#define REP(i, n) for (int i = 0; (i) < (int)(n); ++ (i))
#define REP3(i, m, n) for (int i = (m); (i) < (int)(n); ++ (i))
#define REP_R(i, n) for (int i = (int)(n) - 1; (i) >= 0; -- (i))
#define REP3R(i, m, n) for (int i = (int)(n) - 1; (i) >= (int)(m); -- (i))
#define ALL(x) std::begin(x), std::end(x)
using namespace std;
template <class T, class U> inline void chmin(T & a, U const & b) { a = min<T>(a, b); }

int solve(int n, int m, const vector<string> & p) {
    vector<bool> mergeable(1 << n, true);
    REP (s, 1 << n) {
        if (__builtin_popcount(s) <= 1) {
            // nop
        } else if (__builtin_popcount(s) == 2) {
            int a = __builtin_ctz(s);
            int b = __builtin_ctz(s & ~ (1 << a));
            REP (i, m) {
                if (p[a][i] != '*' and p[b][i] != '*' and p[a][i] != p[b][i]) {
                    mergeable[s] = false;
                }
            }
        } else {
            REP (a, n) if (s & (1 << a)) {
                REP (b, a) if (s & (1 << b)) {
                    if (not mergeable[(1 << a) | (1 << b)]) {
                        mergeable[s] = false;
                    }
                }
            }
        }
    }

    vector<int> dp(1 << n, INT_MAX);
    REP (s, 1 << n) {
        dp[s] = __builtin_popcount(s);
        REP3 (t, 1, s + 1) if ((s & t) == t) {
            if (mergeable[t]) {
                chmin(dp[s], dp[s & ~ t] + 1);
            }
        }
    }
    return dp.back();
}

int main() {
    int n, m; cin >> n >> m;
    vector<string> p(n);
    REP (i, n) {
        cin >> p[i];
    }
    cout << solve(n, m, p) << endl;
    return 0;
}

Submission Info

Judge Result