UVA 12530

UVA12530.cpp

#include <cstdio>
#include <vector>
#include <cstring>
#define MAXN 3000

using namespace std;
char T[60][60];
int r, c, dx[] = {-1, 1, 0, 0}, dy[] = {0, 0, -1, 1};
vector<int> adj[MAXN];
int pi[MAXN];
bool visit[MAXN];

inline bool valid(int i, int j) {
    return i>=0 and j>=0 and i<r and j<c and T[i][j]!='X';
}

int alternatingPath(int u) {
    if(visit[u])  return 0;
    visit[u] = true;
    for(int j=0; j<adj[u].size(); j++) {
        int v = adj[u][j];
        if(pi[v] == -1 or alternatingPath(pi[v])) {
            pi[v] = u;
            return 1;
        }
    }
    return 0;
}

int main() {
    while(scanf("%d %d", &r, &c)!=EOF) {
        for(int i=0; i<r; i++) {
            scanf("%s", T[i]);
            for(int j=0; j<c; j++)
                adj[i*c+j].clear();
        }
        int count = 0;
        for(int i=0; i<r; i++)
            for(int j=0; j<c; j++) {
                count += T[i][j]!='X';
                if((i+j)&1) {
                    int ii, jj;
                    for(int k=0; k<4; k++) {
                        ii = i+dx[k], jj = j+dy[k];
                        if(valid(ii, jj))
                            adj[i*c+j].push_back(ii*c+jj);
                    }
                }
            }
        memset(pi, -1, sizeof pi);
        int ans = 0;
        for(int i=0; i<r*c; i++)
            if(i&1) {
                memset(visit, 0, sizeof visit);
                ans += alternatingPath(i);
            }
        //printf("# %d %d\n", count, ans);
        puts(ans*2==count?"2":"1");
    }
}

UVa OJ judges this submission as "WA"