solution to https://amazon.interviewstreet.com/challenges/dashboard/#problem/4fd6570bd51e1

conn_sets.cpp

#include <iostream>
#include <stdio.h>
#include <string.h>
using namespace std ;
#define _(x,a) memset(x,a,sizeof(x))
#define LET(x,a) __typeof(a) x(a)
#define FOR(i,a,b) for(LET(i,a);i!=(b);++i)
#define REP(i,n) FOR(i,0,n)
#define GI ({int t;scanf("%d",&t);t;})

void crossall(int i,int j,int** mat,int n){
	mat[i][j]=0;															//11		
	if(i-1>=0 && j-1>=0 && mat[i-1][j-1]==1)	{	crossall(i-1,j-1,mat,n);	}  //00
	if(j-1>=0 && mat[i][j-1]==1)				{	crossall(i,j-1,mat,n);		}    //10
	if(i-1>=0 && mat[i-1][j]==1)				{	crossall(i-1,j,mat,n);		}	//01
	if(i+1<n && j+1<n && mat[i+1][j+1]==1)		{	crossall(i+1,j+1,mat,n);	}	//22
	if(j+1<n && mat[i][j+1]==1)					{	crossall(i,j+1,mat,n);		}	//12
	if(i+1<n && mat[i+1][j]==1)					{	crossall(i+1,j,mat,n);		}	//21
	if(i-1>=0 && j+1<n && mat[i-1][j+1]==1)		{	crossall(i-1,j+1,mat,n);	}	//02
	if(i+1<n && j-1>=0 && mat[i+1][j-1]==1)		{	crossall(i+1,j-1,mat,n);	}	//20
}

int main(int argc, char const *argv[])
{
	int N=GI,dim,**mat;
	int solution[N];_(solution,0);
	REP(l,N){
		dim=GI;
		mat=new int*[dim];
		REP(i,dim) mat[i]=new int[dim];
		REP(i,dim)REP(j,dim) mat[i][j]=GI;
		REP(i,dim)REP(j,dim) if(mat[i][j]==1) {solution[l]++;crossall(i,j,mat,dim);}
	} 
	REP(i,N) cout<<solution[i]<<endl;
	return 0;
}