题意:就是八皇后问题的变形,给你八个皇后的位置,问是否满足八皇后的摆放.
注: 任意皇后可以攻击同一行,同一列,同一对角线的其他皇后.
思路: 直接判断所输入的位置是否冲突就可以了,即判断是否后面输入与前面同行，同列或同对角线. 所以用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);
}
