Aizu ALDS1_13_A8 Queens Problem八皇后的路径输出

The goal of 8 Queens Problem is to put eight queens on a chess-board such that none of them threatens any of others. A queen threatens the squares in the same row, in the same column, or on the same diagonals as shown in the following figure.

For a given chess board where kk queens are already placed, find the solution of the 8 queens problem.

Input
In the first line, an integer kk is given. In the following kk lines, each square where a queen is already placed is given by two integers rr and cc. rr and cc respectively denotes the row number and the column number. The row/column numbers start with 0.

Output
Print a 8×88×8 chess board by strings where a square with a queen is represented by 'Q' and an empty square is represented by '.'.

Constraints
There is exactly one solution

Sample Input 1
2
2 2
5 3

Sample Output 1
......Q.
Q.......
..Q.....
.......Q
.....Q..
...Q....
.Q......
....Q...

题意：

　　给出n，代表给出n个确定的棋子数坐标，输出任意一组满足条件的八皇后即可。

不能直接根据斜率进行判断

不知道为什么？？？

int judge(int x)
{
    for(int i=0; i<x; i++) //判断之前和走过的行是否有重复
    {
        int dd1=abs(i-x);
        int dd2=abs(a[i]-a[x]);
        if(dd1==dd2)
        {
            return 1;
        }
    }
    return 0;
    //对角线出现过即k=-1或1
    //即斜率的绝对值=1
    //即两者的横纵坐标对应相减后绝对值相等
}

dfs不知道怎么解释，详细解释看代码上的注释吧。

AC代码：

  1 #include<stdio.h>
  2 #include<string.h>
  3 #include<iostream>
  4 #include<cmath>
  5 using namespace std;
  6 
  7 int a[9];//记录第几行第几列下了棋
  8 int aa[9];//标记行
  9 char s[9][9];//存图，记录输出
 10 int b[9],c[20],d[20];//标记列、斜率>0的对角线、斜率<0的对角线
 11 //对角线需要开的大一点
 12 int flag;
 13 
 14 //int judge(int x)//传入行
 15 //{
 16 //    for(int i=0; i<x; i++) //判断之前和走过的行是否有重复
 17 //    {
 18 //        int dd1=abs(i-x);
 19 //        int dd2=abs(a[i]-a[x]);
 20 //        if(dd1==dd2)
 21 //            return 1;
 22 //    }
 23 //    return 0;
 24 //    //对角线出现过即k=-1或1
 25 //    //即斜率的绝对值=1
 26 //    //即两者的横纵坐标对应相减后绝对值相等
 27 //}
 28 //不知道为什么对角线这样判断会WA
 29 
 30 void dfs(int x)//传入行
 31 {
 32     if(flag==1)
 33         return ;
 34     if(x>7)
 35     {
 36         flag=1;//因为只需要输出一组结果
 37         for(int i=0; i<8; i++)
 38             printf("%s\n",s[i]);
 39         return ;
 40     }
 41 
 42     if(aa[x])//如果该行标记过
 43         dfs(x+1);//则往下一行进行搜索
 44     else
 45     {
 46         //如果该行未被标记过，则在该行进行下棋
 47         for(int j=0; j<8; j++) //决定下在哪一列
 48         {
 49             //a[x]=j;//下上去
 50             //if(b[j]==0&&(judge(x)==0))
 51 
 52             //如果该列没有标记且两条对角线没有标记过
 53             if(b[j]==0&&c[x+j]==0&&d[x-j+8]==0)
 54             {
 55                 c[x+j]=1;
 56                 d[x-j+8]=1;
 57                 b[j]=1;
 58                 s[x][j]='Q';
 59                 dfs(x+1);
 60                 s[x][j]='.';
 61                 b[j]=0;
 62                 c[x+j]=0;
 63                 d[x-j+8]=0;
 64             }
 65         }
 66     }
 67     return ;
 68 }
 69 
 70 int main()
 71 {
 72     std::ios::sync_with_stdio(false);
 73     cin.tie(0);
 74     cout.tie(0);
 75     int t;
 76     while(cin>>t)
 77     {
 78         memset(a,0,sizeof(a));
 79         memset(aa,0,sizeof(aa));
 80         memset(b,0,sizeof(b));
 81         memset(c,0,sizeof(c));
 82         memset(d,0,sizeof(d));
 83         flag=0;
 84         for(int i=0; i<8; i++)
 85         {
 86             for(int j=0; j<8; j++)
 87                 s[i][j]='.';
 88         }
 89         int x,y;
 90         for(int i=0; i<t; i++)
 91         {
 92             cin>>x>>y;
 93             c[x+y]=1;
 94             d[x-y+8]=1;//标记对角线
 95             aa[x]=1;//标记行
 96             a[x]=y;//该点确定下棋了
 97             b[y]=1;//标记列
 98             s[x][y]='Q';//确定改点需要输出
 99         }
100         dfs(0);
101     }
102     return 0;
103 }