題意:就是八皇后問題的變形,給你八個皇后的位置,問是否滿足八皇后的擺放.
注: 任意皇后可以攻擊同一行,同一列,同一對角線的其他皇后.
思路: 直接判斷所輸入的位置是否沖突就可以了,即判斷是否后面輸入與前面同行狂秘，同列或同對角線. 所以用4個數組分別標記下每一個位置看是否沖突就行了.
代碼如下：
#include<cstdio>
void check()
{
int flag=1;
int a[10]={0},b[10]={0},c[25]={0},d[25]={0};
char ch[5];
for(int i=0;i<8;i++){
scanf("%s",ch);
int x=ch[0]-'A'+1;
int y=ch[1]-'0';
if(a[x]) flag=0;//這兩個判斷是否有同行或同列
if(b[y]) flag=0;
if(c[x+y]) flag=0;//判斷是否有同負對角線
if(d[x-y+10]) flag=0;//判斷是否有同正對角線,為了防止出現負數,所以需要加一個數.
a[x]=1,b[y]=1;
c[x+y]=1,d[x-y+10];
}//flag=1,即所有的點都不同行同列或同對角線,即符合八皇后擺放.
if(flag) printf("Valid\n");
else printf("Invalid\n");
}
int main()
{
int t;
scanf("%d",&t);
while(t--){
check();
}
}
再附上擺放8皇后的代碼: (可以推廣到n皇后)
#include<cstdio>
#include<cmath>
#include<algorithm>
const int N=8;
int a[10]; //a[i]存的是放在第i行的皇后的列的坐標.
//我們的思想是每一行放一個皇后. 然后遞歸下去放皇后.
bool check(int *a,int n) //這個是關鍵.
{
for(int i=2;i<=n;i++){
for(int j=1;j<=i-1;j++){
if(a[i]==a[j] || (abs(a[i]-a[j]) == abs(i-j)))
return false;
}
}
return true;
}
int flag=0;
void Queen8(int k)
{
if(flag) return ;
if(k>N){
for(int i=1;i<=N;i++){
printf("(%d,%d)\n",i,a[i]);
}
flag=1; //只打印一種情況.
return ;
}
for(int i=1;i<=N;i++){
a[k]=i;
if(check(a,k)) //如果不沖突,遞歸擺放下一個皇后.
Queen8(k+1);
}
return ;
}
int main()
{
Queen8(1);
}
