Google APAC 2015 University Graduates Test Round C Problem A

RoundC_A.cpp

#include <bits/stdc++.h>
#define Inf 0x3f3f3f3f
using namespace std;

int dir[8][2] = { {-1,-1}, {0,-1}, {1,-1},
                  {-1,0} ,         {1,0},
                  {-1,1} ,  {0,1}, {1,1}  };
char mp[350][350];
int sum[350][350];
int vis[350][350];
int T;
int N;

bool inmap(int i, int j)
{
    return i >= 0 && i < N && j >= 0 && j < N;
}

void dfs(int i, int j){
    if( !inmap(i, j) || sum[i][j] == Inf )
        return;
    if ( sum[i][j] > 0 && sum[i][j] < Inf )
    {
        vis[i][j] = 1;
        return;
    }
    if ( sum[i][j] == 0 )
    {
        vis[i][j] = 1;
        for (int d = 0; d < 8; d++ ){
            int newi = i + dir[d][0];
            int newj = j + dir[d][1];
            if ( inmap( newi, newj ) && vis[newi][newj] == 0 ){
                dfs(newi, newj);
            }
        }
    }
}

int main()
{

    ios_base::sync_with_stdio(0);

    cin >> T;
    int Case = 1;
    while ( T-- ){
        int ans = 0;
        cin >> N;
        memset( mp, 0, sizeof(mp) );
        memset( sum, 0, sizeof(sum) );
        memset( vis, 0, sizeof(vis) );
        for ( int i = 0; i < N; i++ ){
            cin >> mp[i];
        }

        for(int i = 0; i < N; i++ ){
            for(int j = 0; j < N; j++ ){
                if ( mp[i][j] == '.' ){
                    int newi,newj;
                    for(int d = 0; d < 8; d++){
                        newi = i + dir[d][0];
                        newj = j + dir[d][1];
                        if( inmap(newi, newj) && mp[newi][newj] == '*' ){
                            sum[i][j]++;
                        }
                    }
                }
                if ( mp[i][j] == '*' )
                {
                    sum[i][j] = Inf;
                }
            }
        }

        for(int i = 0 ; i < N ; i++ ){
            for (int j = 0 ; j < N ; j++ ){
                if ( sum[i][j] == 0 && vis[i][j] == 0 ){
                    dfs(i,j);
                    ans++;
                }
            }
        }

        for(int i = 0 ; i < N ; i++ ){
            for (int j = 0 ; j < N ; j++ ){
                if ( (sum[i][j] > 0 && sum[i][j] < Inf ) && vis[i][j] == 0 ){
                    vis[i][j] = 1;
                    ans++;
                }
            }
        }
        printf("Case #%d: %d\n", Case++,  ans);
    }
}