DFS

• 一开始考虑用bool标记，但是每次清除标记就会很麻烦，
• 因为bool只有true和false，而一个位置可能被多次标记
• 所以用int型作为标记
• 注意访问一定要判断一下，避免越界导致出错

#include<iostream>
#include<string>
#include<cstring>
using namespace std;
int chess[8][8];//标记
string ans[93];//答案
int k=0;

void getans(string s,int pos){//已经排列坐标、查找行数
    if(pos==8){
        ans[k++].insert(0,s);//成功排列
       
        return ;
    }
    for(int i=0;i<8;i++){//遍历pos这一行
      if(chess[pos][i]==0){//未被访问
        for(int j=pos+1;j<8;j++){//只考虑高于pos行的标记
          chess[j][i]++;//纵向
          if(j+i-pos>=0&&j+i-pos<=7)chess[j][j+i-pos]++;//左上对角
          if(pos+i-j>=0&&pos+i-j<=7)chess[j][pos+i-j]++;//右上对角
        }
        
        char x=i+'1';
        string next(s);
        next.insert(next.end(),1,x);
      
        getans(next,pos+1);//递归
        
        for(int j=pos+1;j<8;j++){//清除本次标记
          chess[j][i]--;
          if(j+i-pos>=0&&j+i-pos<=7)chess[j][j+i-pos]--;
          if(pos+i-j>=0&&pos+i-j<=7)chess[j][pos+i-j]--;
        }
      }
    }
    return;
}

int main(){
  memset(chess,0,sizeof(chess));
    string s;
    getans(s,0);
    int n;
    while(scanf("%d",&n)!=EOF){
        cout<<ans[n-1]<<endl;
    }
}

- 直接判断当前位置是否可行，也可以简化标记过程

• 对角线坐标特点：横纵坐标之和或之差相同

#include<iostream>
#include<string>
#include<cstring>
using namespace std;
const int maxn=8;
bool col[8],lef[2*maxn-1],rig[2*maxn-1];//标记
string ans[93];//答案
int k=0;

void getans(string s,int pos){//已经排列坐标、查找行数
    if(pos==8){
        ans[k++].insert(0,s);//成功排列
        return ;
    }
    for(int i=0;i<8;i++){//遍历pos这一行
      if(!col[i]&&!lef[pos-i+maxn-1]&&!rig[pos+i]){//未被访问
        col[i]=lef[pos-i+maxn-1]=rig[pos+i]=true;
        
        char x=i+'1';
        string next(s);
        next.insert(next.end(),1,x);
      
        getans(next,pos+1);//递归
      
        col[i]=lef[pos-i+maxn-1]=rig[pos+i]=false;//清除本次标记
      }
    }
    return;
}

int main(){
  memset(col,false,sizeof(col));
  memset(rig,false,sizeof(rig));
  memset(lef,false,sizeof(lef));
    string s;
    getans(s,0);
    int n;
    while(scanf("%d",&n)!=EOF){
        cout<<ans[n-1]<<endl;
    }
}