Tuesday, September 17, 2013

Google Codejam 2008 Round 3 - C ( = acmicpc.net 1014)

Link : http://www.acmicpc.net/problem/1014
Link : http://code.google.com/codejam/contest/32002/dashboard#s=p2 (Problem C : No Cheating)

1) Small case(n, m <= 10)
Bitmask Dynamic Programming : O(N^2*(2^(2*N)))
But actual time complexity is much smaller because of the impossible situations.

2) Large case(n,m <= 80)
Bipartite matching , Maximum Flow

#include <iostream>
#include <memory.h>
#include <string>
using namespace std;
int C, N, M;
string bd[100];
int nbx[100][100], nby[100][100], v[100][100];
int T=0;
bool dfs(int a, int b) {
 if (a<0) return true;
 if(v[a][b]==T) return false;
 v[a][b]=T;
 for (int i=a-1;i<=a+1;i++) {
  for (int j=b-1;j<=b+1;j+=2) {
   if (i>=0 && i<M && j>=0 && j<N && bd[i][j]=='.') {
    if (dfs(nbx[i][j], nby[i][j])) {
     nbx[i][j]=a; nby[i][j]=b;
     nbx[a][b]=i; nby[a][b]=j;
     return true;
    }
   }
  }
 }
 return false;
}
int play() {
 memset(nbx,-1,sizeof(nbx));
 memset(nby,-1,sizeof(nby));
 memset(v, -1, sizeof(v)); T=-1;
 int rst=0;
 for(int i=0;i<M;i++) for(int j=0;j<N;j++) {
  if (bd[i][j]=='.') {
   rst++;
   if (j%2) {
    T++;
    if (dfs(i,j)) rst--;
   }
  }
 }
 return rst;
}
int main() {
 cin>>C;
 for (int i=1; i<=C; i++) {
  cin>>M>>N;
  for (int r=0;r<M;r++) cin>>bd[r];
  cout<<play()<<endl;
 }
 return 0;
}

No comments:

Post a Comment