P1219 八皇后问题

说是八皇后问题，其实可以看做一个 N 皇后问题。

搜索思路

一个 dfs，先确定搜索的行，然后确认这一行的每一列的格子，看它能不能放置一个皇后，一旦能够放置皇后，则搜索下一层，直到超出搜索范围，注意每次搜索结束后还要撤销当前搜索时存储的状态。

处理对角线

左上到右下的对角线中，坐标 $i+j$ 都相等，右上到左下的对角线中，坐标 $i-j+n$ 都相等，通过这两个条件即可通过下标判断相应对角线上是否存在皇后。

#include <bits/stdc++.h>
using namespace std;

int a[100];//行
int c[100];//列是否有皇后
int b[100];//左下到右上对角线
int d[100];//右上到左下对角线
int total;
int n;

void print(){
    if(total < 3){
        for(int i = 1;i<=n;i++){
            cout << a[i] << " "; 
        }
        cout << endl;
    }
    total++;
}

void dfs(int i){//i为行数
    if(i > n){//超出范围
        print();
        return;
    }else{
        for(int j = 1;j<=n;j++){//j为列数
            if(b[j] == 0 && c[i+j] == 0 && d[i-j+n] == 0){//因为我选的就是每一行的各个位置，所以这就是默认合法的位置，不需要再特判了
                a[i] = j;
                b[j] = 1;
                c[i+j] = 1;
                d[i-j+n] = 1;
                dfs(i+1);
                b[j] = 0;//?
                c[i+j] = 0;
                d[i-j+n] = 0;
            }
        }
    }
}


int main(int argc, char const *argv[])
{
    cin >> n;
    dfs(1);
    cout << total;
    return 0;
}

P1135 奇怪的电梯

这题是一个 bfs，由于只有上和下两种选择，可以看做是一课二叉树，所以这个 bfs 实质上就是对二叉树的层序遍历，不过这个二叉树是一边遍历一边生成的抽象结构。

#include <bits/stdc++.h>
using namespace std;

struct node{
    int now_level;
    int num;
    int n;
};

int main(int argc, char const *argv[])
{
    int n,a,b;
    cin >> n >> a >> b;
    vector<int> num(n+1);
    vector<int> ans(n+1);
    vector<bool> vis(n+1);
    fill(vis.begin(),vis.end(),false);
    fill(ans.begin(),ans.end(),INT32_MAX);
    for(int i = 1;i<=n;i++){
        cin >> num[i];
    }

    queue<node> q;
    vis[a] = true;
    int now = a;
    q.push({a,num[a],0});
    while(!q.empty()){
        node cur = q.front();
        q.pop();
        if(cur.now_level == b){
            cout << cur.n << endl;
            return 0;
        }
        int up = cur.now_level + cur.num;
        int down = cur.now_level - cur.num;
        if(up <= n && !vis[up]){
            vis[up] = true;
            q.push({up,num[up],cur.n+1});
        }
        if(down > 0 && !vis[down]){
            vis[down] = true;
            q.push({down,num[down],cur.n+1});
        }
    }
    cout << "-1" << endl;
    return 0;
}