ACM ICPC 2013 A – Attacking rooks

Problem: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=602&page=show_problem&problem=4406

Wiki Theory: http://en.wikipedia.org/wiki/Matching_(graph_theory)

#include <iostream>
#include <vector>
#include <stdio.h>
#include <string.h>
using namespace std;

typedef long long   LL;

struct bipartite_graph {
    int V1, V2, *match;
    vector<int> *L;
    bool *visited;

    bipartite_graph(int MAX_V1, int MAX_V2){
        L = new vector<int>[MAX_V1];
        visited = new bool[MAX_V2];
        match = new int[MAX_V2];
    }

    void clear(int _V1, int _V2){
        V1 = _V1;
        V2 = _V2;
        for(int i=0; i<V1 ;++i)
        	L[i].clear();
    }

    void add_edge(int v1, int v2){
        L[v1].push_back(v2);
    }

    bool dfs(int u) {
        for(int i=L[u].size()-1;i>=0;--i){
            int v = L[u][i];
            if(!visited[v]){
                visited[v] = true;
                if(match[v]==-1 || dfs(match[v])){
                    match[v] = u;
                    return true;
                }
            }
        }
        return false;
    }

    int maximum_matching() {
        int ans = 0;
        fill(match,match+V2,-1);
        for(int i=0;i<V1;++i){
            fill(visited,visited+V2,false);
            ans += dfs(i);
        }
        return ans;
    }
} G(10000, 10000);
int R[100][100], C[100][100];

int main() {
	int N, V1, V2;
	while(scanf("%d", &N) == 1) {
		vector<string> vs(N);
		V1 = V2 = 0;
		memset(R, -1, sizeof(R));
		memset(C, -1, sizeof(C));
		for(int i=0; i<N ;i++)
			cin >> vs[i];
		G.clear(10000, 10000);

		for(int i=0; i<N ;i++) {
			for(int j=0; j<N ;j++) {
				if(vs[i][j] == 'X') continue;
				if(j == 0) {
					R[i][j] = V1++;
				}
				else {
					if(R[i][j-1] == -1) R[i][j] = V1++;
					else R[i][j] = R[i][j-1];
				}
				if(i == 0) {
					C[i][j] = V2++;
				}
				else {
					if(C[i-1][j] == -1) C[i][j] = V2++;
					else C[i][j] = C[i-1][j];
				}
				G.add_edge(R[i][j], C[i][j]);
			}
		}

		printf("%dn", G.maximum_matching());
	}
}