gcj17qD

//AC GCJ 2017qualD https://code.google.com/codejam/contest/3264486/dashboard#s=p3
//nasarouf@cs.ubc.ca
#include <cstdio>
#include <string>
#include <iostream>
#include <sstream>
#include <cmath>
#include <map>
#include <set>
#include <functional>
#include <vector>
using namespace std;

//usage: Flow<int> f(n); /*make graph using f.conn...*/ f.reserflow(); f.flow(0,1); f.f[][] wil have the flow values

#define MAX 404

template<class Node, class adjType, class fromType>
bool bfs(Node a, Node b, const adjType &adj, function<bool(int, int)> rc, fromType &from) {
    static Node q[MAX]; int qh = 0, qt = 0; q[qh++] = a;
    static map<Node, int> visited; static int flag = 0;
    visited[a] = ++flag;
    while (qh > qt) {
        a = q[qt++]; if (a == b) return true;
        for (Node j : adj[a]) {
            if (rc(a, j) && visited[j] != flag) {
                visited[j] = flag; q[qh++] = j; from[j] = a;
                if (j == b) return true;
            }
        }
    }
    return false;
}

template<class T>
class Flow {
public:
    int n;
    vector<set<int>> adj;
    vector<vector<T>> c, f;

    inline void connect(int a,int b,T cap) {adj[a].insert(b);adj[b].insert(a);c[a][b]=(cap);}
    inline void disconnect(int a,int b) {adj[a].erase(b);adj[b].erase(a);c[a][b]=0;}
    inline void conn(int a, int b) { connect(a, b, 1); }
    inline T residual(int i, int j){ return (c[i][j] - f[i][j]); }

    Flow(int _n=0):n(_n),adj(n,set<int>()), c(n, vector<T>(n, (T)0)), f(n, vector<T>(n, (T)0)) {}
    void resetflow() { for (int i = 0; i < n; i++) for (auto j : adj[i]) f[i][j] = 0; }
    T flow(int src = 0, int sink = 1) {
        vector<int> from(n,0);
        const auto &cc = c, &ff = f;
        while (bfs(src, sink, adj, [=,&cc,&ff](int i, int j) mutable {return ((cc[i][j] - ff[i][j]) > 0); }, from)){
            for (int b = 1; b != 0; b = from[b]){ f[from[b]][b] += 1; f[b][from[b]] -= 1; }
        }
        T sm = 0; for (int i = 2; i < n; i++) sm += f[0][i];
        return sm;
    }
};

char board[MAX][MAX], inboard[MAX][MAX];

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    int t, n, m;  cin >> t; for (int u = 0; u < t; u++) {
        cin >> n >> m; for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) board[i][j] = inboard[i][j] = '.';
        char s[100];
        for (int i = 0; i < m; i++) {
            int r, c; cin >> s >> r >> c; r--; c--;
            board[r][c] = inboard[r][c] = s[0];
        }
        {//x
            int N = n; Flow<int> f(N + N + 2);
            /* MAKE THE GRAPH */
            for (int i = 0; i < N; i++) {
                f.conn(0, 2 + i);
                f.conn(2 + N + i, 1);
                for (int j = 0; j < N; j++) f.conn(2 + i, 2 + N + j);
            }
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) if (board[i][j] == 'x' || board[i][j] == 'o') {
                    f.disconnect(0, 2 + i);
                    f.disconnect(2 + i, 2 + N + j);
                    f.disconnect(2 + N + j, 1);
                }
            }
            f.flow();
            for (int i = 0; i < N; i++) if (f.f[0][2 + i] > 0) for (int j = 0; j < N; j++)
                if (f.f[2 + i][2 + N + j] > 0 && f.f[2 + N + j][1] > 0)
                    if (board[i][j] == '+' || board[i][j] == 'o') board[i][j] = 'o'; else  board[i][j] = 'x';
        }
        {//+
            map<pair<int, int>, pair<int, int>> ij2ab;
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    ij2ab[make_pair(i + j, i - j + n - 1)] = make_pair(i, j);
                }
            }
            int N = 2 * n - 1; Flow<int> f(N + N + 2);
            /* MAKE THE GRAPH */
            for (int i = 0; i < N; i++) {
                f.conn(0, 2 + i);
                f.conn(2 + N + i, 1);
                for (int j = 0; j < N; j++) {
                    if (ij2ab.find(make_pair(i, j)) == ij2ab.end()) continue;
                    f.conn(2 + i, 2 + N + j);
                }
            }
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) {
                    if (ij2ab.find(make_pair(i, j)) == ij2ab.end()) continue;
                    int a = ij2ab[make_pair(i, j)].first;
                    int b = ij2ab[make_pair(i, j)].second;
                    //cout << i << "," << (j-(n-1)) << "=" << a << "," << b << endl;
                    if (board[a][b] == '+' || board[a][b] == 'o') {
                        f.disconnect(0, 2 + i);
                        f.disconnect(2 + i, 2 + N + j);
                        f.disconnect(2 + N + j, 1);
                    }
                }
            }
            f.flow();
            for (int i = 0; i < N; i++) if (f.f[0][2 + i]) for (int j = 0; j < N; j++) if (f.f[2 + i][2 + N + j]) {
                if (ij2ab.find(make_pair(i, j)) == ij2ab.end()) continue;
                int a = ij2ab[make_pair(i, j)].first;
                int b = ij2ab[make_pair(i, j)].second;
                if (board[a][b] == 'x' || board[a][b] == 'o') board[a][b] = 'o'; else  board[a][b] = '+';
            }
        }
        //for (int i = 0; i < n; i++) {
        //  for (int j = 0; j < n; j++) cout << board[i][j];
        //  cout << endl;
        //}

        int tot = 0, cnt=0;
        for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) {
            if (board[i][j] == 'o') tot += 2; else if (board[i][j] != '.') tot++;
            if (board[i][j] != inboard[i][j]) cnt++;
        }
        cout << "Case #" << (u + 1) << ": " << tot << " " << cnt << endl;
        for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) {
            if (board[i][j] != inboard[i][j]) cout << board[i][j] << " " << (i + 1) << " " << (j + 1) << endl;
        }
        cerr << ".";
    }
    return 0;
}