Gym - 100947B 八皇后变形题

题意:就是八皇后问题的变形,给你八个皇后的位置,问是否满足八皇后的摆放.
注: 任意皇后可以攻击同一行,同一列,同一对角线的其他皇后.

思路: 直接判断所输入的位置是否冲突就可以了,即判断是否后面输入与前面同行，同列或同对角线. 所以用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);
}