zoj 1008

本文主要是介绍zoj 1008，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

#include <iostream>
using namespace std;
int n,k[25],t; 
int s[25][4];
int count[25];
//是在组织过后的图上进行DFS，直接搜索会有重复的


bool canT(int x)
{
int i;
if(x==n*n)
return true;
for(i=0;i<t;i++)
{
if(count[i]>0)
{
if(x/n!=0 && s[i][0]!=s[k[x-n]][2])
continue;
if(x%n!=0 && s[i][3]!=s[k[x-1]][1])
continue;
count[i]--;
k[x]=i;
if(canT(x+1))
return true;
else
count[i]++;
}
}
return false;
}


int main()
{
int num=1;
while(cin >> n && n!=0)
{
int i,j;
t=0;
for(i=0;i<25;i++)
{
k[i]=-1;
count[i]=0;
}
for(i=0;i<n*n;i++)
{
cin >> s[t][0] >> s[t][1] >> s[t][2] >> s[t][3];
for(j=0;j<t;j++)
{
if(s[j][0]==s[t][0] && s[j][1]==s[t][1] && s[j][2]==s[t][2] && s[j][3]==s[t][3])
break;
}
if(j<t)
count[j]++;
else
{
count[t]++;
t++;
}
}
if(num!=1)
cout << endl;
cout << "Game " << num << ": ";
num+=1;
if(n==1)
{
cout << "Possible" << endl;
continue;
}
if(canT(0))
cout << "Possible" << endl;
else
cout << "Impossible" << endl;
}
return 0;
}

这篇关于zoj 1008的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---