【图的深度优先遍历搜索】ZOJ1008--Gnome Tetravex

【问题描述】

在N*N（0<=n<=5）的方格中，每一个方格有四个三角形按照上右下左的顺序次序排列，然后移动方格，是那些相邻的方格，满足相邻的对应三角形的值相等，有时候是无解的，有时候有解，题目就是让写下程序来判断给定一个方格看看是否能满足题意，如果能就打印possibble。
如果不能就打印impossible。
输入样例
2
5 9 1 4
4 4 5 6
6 8 5 4
0 4 4 3
2
1 1 1 1
2 2 2 2
3 3 3 3
4 4 4 4
输出样例
Game 1： Possible

Game 2： Impossible

【代码实现】

#include
using namespace std; 
int n;   //方格矩阵的大小
int q;	 //方格的类型数
int iSquare[25][4];   //游戏的方格矩阵
int iCount[25];	   //存放方格的类型，方格类型最多为25个
int iTable[25];    //存放解决方案，实际放置的方格

int Place(int iPos)  //iPos是方格的编号
{
	int i;
	//所有的方格都搜索完毕，全部都是符合要求的
	if(iPos == n * n) return 1;
	//对q种方格类型，每一个都往iPos位置放置一下，判断是否符合要求
	for(i = 0; i < q; i++)	
	{
	    //该类型的方格已经用完了
		if(iCount[i] == 0) continue;
		//如果该方格不在矩阵的最左边，水平相邻的两个三角形数字相比
		if(iPos % n != 0)
			if(iSquare[iTable[iPos-1]][1] != iSquare[i][3])
				continue;
		//如果该方格不在矩阵的最上边，垂直相邻的两个三角形数字相比
		if(iPos >= n)
			if(iSquare[iTable[iPos-n]][2] != iSquare[i][0])
				continue;
	    //iPos位置就放上第i个方格
		iTable[iPos] = i;
		//这种类型的方格数目减1（即使用1个）
		iCount[i]--;
		if(Place(iPos + 1) == 1) return 1;
		//恢复该方格的类型数1个，便于下一次搜索
		iCount[i]++;
	}
	return 0;
}

int main()  
{
	int i, j;
	int iCase = 0;
	int top, right, bottom, left;
	while(cin>>n)  
	{
		iCase++;
		q = 0;
		for(i = 0; i < n * n; i++)	
		{
			cin>>top>>right>>bottom>>left;
			//判断重复的方格类型，q是现有的方个数
			for (j=0; j<q; j++){
			    //如果方格类型是相同的
				if(iSquare[j][0] == top && iSquare[j][1] == right &&
				   iSquare[j][2] == bottom && iSquare[j][3] == left)
				{   //该方格的类型数+1
					iCount[j]++; 
					break;
				}
			}
			//如果读取的方格类型与原有的方格类型不重复，则新增1个
			if(j == q)	
			{
				iSquare[j][0] = top;
				iSquare[j][1] = right;
				iSquare[j][2] = bottom;
				iSquare[j][3] = left;
				iCount[j] = 1;    //该方格的类型数+1
				q++;             //方格的类型数目+1
			}
		}
		if(iCase > 1) cout<<endl;
		if(Place(0) == 1) cout<<"Game "<<iCase<<": Possible"<<endl;
		else cout<<"Game "<<iCase<<": Impossible"<<endl;
	}
	return 0;
}