题解 | #八皇后#

//我竟然自己写出来了
/*
DFS的形态千变万化，没有定数，但掌握基本框架就能以不变应万变：

DFS里面要先写上返回条件，也就是该方案算到底成功了，就返回。
然后就对所有路径进行枚举，排除掉不对的方案后，调用下一层DFS。
一条路径算到底之后才会算其他路径，因此，有关上一条路径做的标记要全部还原，再进入下一条路径的寻找。
*/

/*
字符串不初始化会发生段错误
*/

#include <iostream>
#include <cstring>
using namespace std;

string answer[92];//共92个答案
int xb=0;//当前答案下标

int chess[9];//第i行的皇后放在了第几列上


void DFS(int row)//当前放好的皇后的行号，1
{
    if(row==8)//1~8行的皇后都放好了
    {
        for(int i=1;i<=8;i++)
        {
            char lie=chess[i]+'0';
            answer[xb]+=lie;
        }
        
        xb++;
        return;
    }

    for(int j=1;j<=8;j++)//下一行的皇后可以放在1~8列上
    {
        int flag=1;//这一行的皇后能放在第j列上
        for(int i=1;i<=row;i++)//不能和1~row行皇后在同一列或者同一斜线上
        {
            //i,chess[i]
            //row+1,j
            if(chess[i]==j||abs(row+1-i)==abs(j-chess[i]))
            {
                flag=0;
                break;
            }
        }
        if(flag==1)//当前方案可行
        {
            chess[row+1]=j;//记录
            DFS(row+1);
            chess[row+1]=0;//这个方案的答案已经算到底了，就可以把原来有关这个方案的标记全都还原了
        }

    }

}


int main() {
    int b;
    
    while (cin >> b) {
        memset(chess,0,sizeof(chess)); 
        for(int i=0;i<92;i++)
        answer[i]="";//字符串不能为空！！！必须要先赋值，否则会发生段错误
        for(int i=1;i<=8;i++)
        {
            chess[1]=i;//第一行皇后分别放在1~8列上
            DFS(1);//当前皇后行号
            chess[1]=0;
        }
        
        cout << answer[b-1] << endl;
    }
}