SRM 527 DIV1 450 P8XMatrixRecovery

2部グラフのマッチングまでは、気付いてた。あと一歩だった。
"ある条件を満たす辞書順最小のものを求めよ。"という問題はgreedyで解ける場合が多いような気がする。

int r;
int c;
bool edge[60][60];
bool used[60];
int pr[60];

class P8XMatrixRecovery {
    bool dfs(int s) {
        used[s] = 1;

        REP(v, 2*c) {
            if (!edge[s][v])
                continue;
            int w = pr[v];
            if (w == -1 || (!used[w] && dfs(w))) {
                pr[s] = v;
                pr[v] = s;
                return true;
            }
        }
        return false;
    }

    int match(vector<string> &rows, vector<string> &cols) {
        memset(edge, 0, sizeof(edge));
        REP(i, c) REP(j, c) {
            edge[i][j+c] = edge[j+c][i] = 1;
            REP(k, r) {
                if (cols[j][k] != '?' && rows[k][i] != '?' && rows[k][i] != cols[j][k]) {
                    edge[i][j+c] = edge[j+c][i] = 0;
                    break;
                }
            }
        }

        int ret = 0;
        memset(pr, -1, sizeof(pr));
        REP(i, 2*c) {
            if (pr[i] >= 0)
                continue;
            memset(used, 0, sizeof(used));
            if (dfs(i))
                ++ret;
        }

        return ret;
    }

public:
    vector<string> solve(vector<string> rows, vector<string> columns) {
        r = rows.size();
        c = rows[0].length();

        REP(i, r) REP(j, c) {
            if (rows[i][j] == '?') {
                rows[i][j] = '0';

                if (match(rows, columns) < c)
                    rows[i][j] = '1';
            }
        }

        return rows;
    }
};