51nod-1388-六边形平面（dfs）

多组测试数据，第一行一个整数T，表示测试数据数量，1<=T<=5每组测试数据有相同的结构构成：每组数据第一行一个整数N，表示网格大小，其中1<=N<=50.之后有一个N*N的字符矩阵A，其中A(i,j)为‘X’表示网格中坐标为(i,j)的格子需要被上色，否则不用。Output
每组数据一行输出，即最少需要的颜色数量.Input示例
33---------4-X-----X-----X--4XXXX---X---X---XOutput示例
012孔炤 (题目提供者) 两种情况：（1）三个需要染色的方块连在一起，即三个方块有一个公共顶点，此时一定需要三种颜色（2）出现环的情况，此时有两种情况，奇数个方块和偶数个方块构成的环，答案是不同的for example：一个4x4的方格：    -xxxx--xx--x-xx-      此时有9个方格构成环形，不难看出需要三中颜色；
#include<stdio.h>#include<string.h>#include<algorithm>using namespace std;int dx[7]={-1,1,0,0,1,-1};int dy[7]={0,0,1,-1,-1,1};int used[55][55];char s[55][55];int n,ans;int dfs(int x,int y){	int tmp=0;	if(s[x][y]=='X')		tmp++;	if(y+1<=n && s[x][y+1]=='X')		tmp++;	if(x+1<=n && s[x+1][y]=='X')		tmp++;	else if(x-1>0 && y+1<=n && s[x-1][y+1]=='X')		tmp++;	return tmp;}void find(int a,int b,int x,int y,int num){	int i;	for(i=0;i<6;i++)	{		int t1=x+dx[i];		int t2=y+dy[i];		if(t1<1 || t1>n)			continue;		if(t2<1 || t2>n)			continue;		if(used[t1][t2]==1)		{			if(t1==a && t2==b && num>2)				if(num%2)				{					ans=3;					return;				}			continue;		}		if(s[t1][t2]=='X')		{		   used[t1][t2]=1;		   find(a,b,t1,t2,num+1);		}	}	return;}int  main(){	int T,i,j,res;	scanf("%d",&T);	while(T--)	{		ans=0;		res=0;		scanf("%d",&n);		for(i=1;i<=n;i++)			for(j=1;j<=n;j++)				scanf(" %c",&s[i][j]);		for(i=1;i<=n;i++)			for(j=1;j<=n;j++)			{					res=dfs(i,j);					ans=max(ans,res);					if(ans==3)						break;			}		if(ans<3)		{			for(i=1;i<=n;i++)				for(j=1;j<=n;j++)				{					if(s[i][j]=='X')					{					      memset(used,0,sizeof(used));					      used[i][j]=1;					      find(i,j,i,j,1);					}				}		}		PRintf("%d/n",ans);	}}