LOJ: 1150-Ghosts ( Bipartite Matching+BS )

LOJ: 1150-Ghosts ( Bipartite Matching+BS )
///==================================================///
///                HELLO WORLD !!                    ///
///                  IT'S ME                         ///
///               BISHAL GAUTAM                      ///
///         [ bsal.gautam16@gmail.com ]              ///
///==================================================///
#include<bits/stdc++.h>
#define X first
#define Y second
#define mpp make_pair
#define nl printf("\n")
#define SZ(x) (int)(x.size())
#define pb(x) push_back(x)
#define pii pair<int,int>
#define pll pair<ll,ll>
///---------------------
#define S(a) scanf("%d",&a)
#define P(a) printf("%d",a)
#define SL(a) scanf("%lld",&a)
#define S2(a,b) scanf("%d%d",&a,&b)
#define SL2(a,b) scanf("%lld%lld",&a,&b)
///------------------------------------
#define all(v) v.begin(),v.end()
#define CLR(a) memset(a,0,sizeof(a))
#define SET(a) memset(a,-1,sizeof(a))
#define fr(i,a,n) for(int i=a;i<=n;i++)
using namespace std;
typedef long long ll;
///int month[]={-1,31,28,31,30,31,30,31,31,30,31,30,31}; //Not Leap Year
int dx[]= {1,0,-1,0};
int dy[]= {0,1,0,-1}; //4 Direction
///int dx[]={1,1,0,-1,-1,-1,0,1};int dy[]={0,1,1,1,0,-1,-1,-1};//8 Direction
///int dx[]={2,1,-1,-2,-2,-1,1,2};int dy[]={1,2,2,1,-1,-2,-2,-1};//Knight Direction
///==========CONSTANTS=============///
///  Digit     0123456789012345678 ///
#define MX     105
#define inf    1000000010
#define MD     1000000007
#define eps    1e-9
///===============================///

vector<int>G[MX+5];
int lft[MX+5],rgt[MX+5],dis[MX+5];

int BFS(int n) {
    queue<int>Q;
    for(int i=1; i<=n; i++) {
        if(lft[i]==0) {
            dis[i]=0;
            Q.push(i);
        } else dis[i]=inf;
    }
    dis[0]=inf;
    while(!Q.empty()) {
        int u=Q.front();
        Q.pop();
        for(int i=0; i<SZ(G[u]); i++) {
            int v=G[u][i];
            if( dis[ (rgt[v]) ] == inf ) {
                dis[ (rgt[v]) ]=dis[u]+1;
                Q.push( rgt[v] );
            }
        }
    }
    return (dis[0]!=inf);
}

int DFS(int u) {
    if(u==0) return 1;
    for(int i=0; i<SZ(G[u]); i++) {
        int v=G[u][i];
        if( dis[ (rgt[v]) ]==dis[u]+1 && DFS(rgt[v]) ) {
            lft[u]=v;
            rgt[v]=u;
            return 1;
        }
    }
    dis[u]=inf;
    return 0;
}

int Hopcroft_Match(int n) {
    CLR(lft);
    CLR(rgt);
    int match=0;
    while(BFS(n)) {
        for(int i=1; i<=n; i++) {
            if(lft[i]==0 && DFS(i) ) {
                match++;
            }
        }
    }
    return match;
}

void show_match(int n) {
    for(int i=1; i<=n; i++) {
        printf("%d ---> %d\n",i,max(0,lft[i]-n));
    }
}

int n,gh,hm;
char s[MX][MX];
int id[MX][MX];
int dp[MX][MX];
int mat[MX][MX];

void Bfs(int x,int y,int g) {
    fr(i,1,n)fr(j,1,n)dp[i][j]=inf;
    queue< pii >Q;
    Q.push( mpp(x,y) );
    dp[ x ][ y ]=0;
    while( !Q.empty() ) {
        pii p=Q.front();
        Q.pop();
        int x=p.X,y=p.Y;
        if( s[x][y]=='H' ) {
            mat[ g ][ id[x][y] ]=2*dp[x][y]+2;
        }
        for(int i=0; i<4; i++) {
            int nx=x+dx[i];
            int ny=y+dy[i];
            if( nx>=1 && nx<=n && ny>=1 && ny<=n && s[nx][ny]!='#' ) {
                if( dp[ nx ][ ny ]>dp[ x ][ y ]+1 ) {
                    dp[ nx ][ ny ]=dp[ x ][ y ]+1;
                    Q.push( mpp(nx,ny) );
                }
            }
        }
    }
}

bool Ok(int d) {
    fr(i,1,MX)G[i].clear();
    fr(i,1,gh) {
        fr(j,1,hm) {
            if( mat[i][j]<=d ) {
                G[ i ].pb( gh+j );
                G[ j+gh ].pb( i );
            }
        }
    }
    int mt=Hopcroft_Match(gh);
    return (mt==hm);
}

int main() {
    int i,j,k,x,y,z,tc,cs=1;
    S(tc);
    while(tc--) {
        S(n);
        gh=hm=0;
        fr(i,1,n) {
            fr(j,1,n) {
                cin>>s[i][j];
                if( s[i][j]=='H' ) {
                    id[i][j]=++hm;
                }
                if( s[i][j]=='G' ) {
                    id[i][j]=++gh;
                }
            }
        }
        fr(i,1,gh)fr(j,1,hm)mat[i][j]=inf;
        fr(i,1,n) {
            fr(j,1,n) {
                if( s[i][j]=='G' ) {
                    Bfs(i,j,id[i][j]);
                }
            }
        }
        int lo=2,hi=inf-5,ret=-1;
        while( lo<=hi ) {
            int md=(lo+hi)>>1;
            if( Ok(md) ) {
                ret=md;
                hi=md-1;
            } else lo=md+1;
        }
        printf("Case %d: ",cs++);
        if(ret==-1) printf("Vuter Dol Kupokat\n");
        else printf("%d\n",ret);
    }
    return 0;
}