Viewing Text Document

Title:

Owner: Andrian Kurniady

Last updated on: Tuesday, 15 July 2008

Description:

Content:

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

char buffer[150][150];
int dpmat[150][150];
int m,n;

void fill(int x, int y, int color){
    if (!dpmat[x][y]){
                
        dpmat[x][y]=color;
    
        if (x>0 && buffer[x-1][y]=='.'){
            fill(x-1,y,color);
        }
        if (y>0 && buffer[x][y-1]=='.'){
            fill(x,y-1,color);
        }
        if (x+1<m && buffer[x+1][y]=='.'){
            fill(x+1,y,color);
        }
        if (y+1<n && buffer[x][y+1]=='.'){
            fill(x,y+1,color);
        }
    
    }
}

int main(){
    int ntc;
    scanf("%d",&ntc);
    while (ntc--){
        scanf("%d%d", &m,&n);
        for (int i=0;i<m;i++){
            scanf("%s", buffer[i]);
        }
        memset(dpmat, 0, sizeof(dpmat));
        
        int color=1;
        
        for (int i=0;i<m;i++)
        for (int j=0;j<n;j++){
            if (buffer[i][j]=='.' && !dpmat[i][j]){
                fill(i,j, color); 
                color++;
            }
        }
        
        long long res=0;
        for (int c=1;c<color;c++){
            long long cc=0;
            for (int i=0;i<m;i++)
            for (int j=0;j<n;j++){
                if (dpmat[i][j]==c) cc++;
            }
            res+=cc*(cc-1)/2;
        }   
        printf("%I64d\n", res);             
    }
    
    return 0;
}