王道机试指南搜索

例题9.1玛雅人的密码（清华大学上机）
利用一个mp来标记是否出现过，之后进行BFS，且每一次shift之后mp都将加1

#include<iostream>
#include<cstdio>
#include<queue>
#include<string>
#include<vector>
#include<map> 
using namespace std;
map<string, int> mp;//记录每一个字符的交换次数 
queue<string> que;//用于bfs的队列 
int n;
string s;
bool has_2012(string s){ //判断是否含有2012 
    for(int i = 0; i < n - 3; i++){
        if(s[i] == '2' && s[i+1] == '0' && s[i+2] == '1' && s[i+3] == '2')
            return true;
    }
    return false;
}
string shift(string s, int i){//用来转换字符串 , i位与i+1交换 
        char temp = s[i];
        s[i] = s[i+1];
        s[i+1] = temp;
        return s;
}
int bfs(string s){
    string newstr;
    mp.clear();
    while(!que.empty()) que.pop();//清空队列，队列没有clear（）函数 
    que.push(s);//初始字符串入队 
    mp[s] = 0;//初始字符串交换次数为0 
    while(!que.empty()){
        s = que.front();
        que.pop();//取出队首 
        for(int i = 0; i < n - 1; i++){
            newstr = shift(s, i);
            if(mp.find(newstr) == mp.end()){//字符没有出现过 
                mp[newstr] = mp[s] + 1;//出现了且交换次数多于他爹的交换次数 
                if(has_2012(newstr)) return mp[newstr];
                else que.push(newstr);
            }
        }
    }
    return -1;
}

int main(){
    while(cin >> n >> s){
        if(has_2012(s)) cout << 0 << endl;
        else cout << bfs(s) << endl;
    }
    return 0;
}  

习题9.2神奇的口袋（北京大学上机）
因为不可以重复，所以可以不用visit数组，直接使用pos来进行遍历，递归就可以得到结果。

#include<iostream>
#include<cstdio>
#include<vector>
using namespace std;
int n;
vector<int> v;
int kind;
void dfs(int sum, int pos){
    if(sum == 40){
        kind++;
        return;
    }
    if(sum > 40) return;
    for(int i = pos; i < n; i++){
            dfs(v[i] + sum, i+1);
    }
} 
int main(){
    while(cin >> n){
        kind = 0;
        v.clear();
        for(int i = 0; i < n; i++){//输入n个数到v 
            int temp;
            cin >> temp;
            v.push_back(temp);
        }
        dfs(0, 0);
        cout << kind << endl;
    }
    return 0;
}  

习题9.2八皇后（北京大学上机）
注意理解题目中的递归思想，剪枝的技巧

#include<iostream>
#include<cstdio>
#include<vector>
#include<algorithm>
#include<string>
#include<cmath>
#include<stdlib.h>
using namespace std;
int p[9];
vector<int> vi;
bool hashtable[9];//用来标记列是否放入 
void generatep(int row){//从第index行开始填入 
    if(row == 9){//表示找到一个结果，将其转化为整数存入vi
        int sum = 0;
        for(int i = 1; i <= 8; i++){
            sum += p[i] * pow(10, 8 - i);
        }
        vi.push_back(sum);
        return;
    }
    
    for(int x = 1; x <= 8; x++){//遍历第x列 
        if(hashtable[x] == false){
            bool flag = true;
            /*for循环用来剪枝*/ 
            for(int pre = 1; pre < row; pre++){//遍历之前填入的结点
            //x为index的列，p[pre]为pre的列 
                if(abs(row - pre) == abs(x - p[pre])){//对角线上的结点相同 
                    flag = false;
                    break;
                }
            }
            if(flag){//可以填入，直接向下填入，递归访问 
                p[row] = x;
                hashtable[x] = true;
                generatep(row+1);
                hashtable[x] = false;//回溯还原 
            }
        }
    }
}
int main(){
    int b;//根本就没有case个数的输入 
    while(cin >> b){
        generatep(1); 
        sort(vi.begin(), vi.end());
        cout << vi[b - 1]<< endl;
    }
    return 0;
}