【数据结构】搜索树

Alex_Shen
2020-12-08 / 0 评论 / 0 点赞 / 56 阅读 / 6,125 字 / 正在检测是否收录...
温馨提示:
本文最后更新于 2022-04-06,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

问题 A: 过河问题–搜索树

题目描述

多个囚犯参与者要过河,其中只有监管者一人可以划船。小船每次最多载两人过河。监管者不在时,已有积怨的囚犯可能会斗殴。请问他们该如何安全过河?
假设一开始所有人都在河的左岸,用0表示,如果成功过河,则到达河的右岸,用1表示。
请采用BFS求解,并输出过河过程。

输入

首先输入要过河的人数n(包括监管者和囚犯)
接着输入监管者的编号s(假设每个人的编号从0开始,编号最小的在最右边)
然后输入有积怨的囚犯的对数m
接下来m行,两两输入有积怨的囚犯编号

输出

如有解,输出划船过河方案,即每一步的状态,也就是每个人此时在河的左岸还是右岸。初始状态全部为0。
否则,输出No solution

样例输入

4
3
2
0 1
1 2

样例输出

0000
1010
0010
1011
0001
1101
0101
1111

题解

#include <iostream>
#include <queue>
#include <vector>
#include <string>
#include<list>
#include<stack>
#include <cstring>
using namespace std;

class node
{
public:
    int* state;
    node* pre;
    node(int n)
    {
        state = new int[n];
        for (int i = 0; i < n; i++)
            state[i] = 0;
    }
};

class problem {
public:
    int num, managerIndex, pairNum;
    int pair1[100], pair2[100];
    queue<node*> list;
    vector<node*> visited;
    problem() {
        cin >> num >> managerIndex >> pairNum;
        for (int i = 0; i < pairNum; i++) {
            cin >> pair1[i] >> pair2[i];
        }
    }
    bool check(node* p)
    {
        for (int i = 0; i < num; i++)
            if (p->state[i] != 1)
                return false;
        return true;
    }

    bool check2(node* p1, node* p2)
    {
        for (int i = 0; i < num; i++)
            if (p1->state[i] != p2->state[i])
                return false;
        return true;
    }

    void print(node* p)
    {
        stack<node*> s;
        node* node = p;
        while (node) {
            s.push(node);
            node = node->pre;
        }
        while (!s.empty()) {
            for (int i = 0; i < num; i++)
                cout << s.top()->state[i];
            s.pop();
            cout << endl;
        }
    }

    void check_situation1(int i1,int i2,node* n) {
        if (i1 == i2){
            if (n->state[i1] == 1)
                n->state[i1] = 0;
            else
                n->state[i1] = 1;
        }
        else if (n->state[i1] == n->state[i2]) {
            if (n->state[i1] == 1)
                n->state[i1] = 0;
            else
                n->state[i1] = 1;
            if (n->state[i2] == 1)
                n->state[i2] = 0;
            else
                n->state[i2] = 1;
        }
        else {
            return;
        }
    }
    
    bool check_if_fight(bool flag, node* n,int i1) {
        for (int j = 0; j < pairNum; j++) {
            int i_ = num - pair1[j] - 1;
            int i__ = num - pair2[j] - 1;
            if ((n->state[i1] != n->state[i_]) && (n->state[i_] == n->state[i__])) {
                flag = true;
                visited.push_back(n);
                break;
            }
        }
        return flag;
    }

    void push(node* p, int i)
    {
        node* n = new node(num);
        for (int j = 0; j < num; j++)
            n->state[j] = p->state[j];
        n->pre = p;
        int index1 = num - managerIndex - 1;
        int index2 = i;
        check_situation1(index1, index2, n);
        bool flag = false;
        for (int j = 0; j < visited.size(); j++) {
            if (check2(n, visited[j])) { 
                flag = true; 
                break; 
            }
        }
        if (!check_if_fight(flag, n, index1))
            list.push(n);
    }

    void bfs() {
        node* start = new node(num);
        start->pre = NULL;
        list.push(start);
        while (!list.empty()) {
            if (check(list.front())) { 
                print(list.front());
                return; 
            };
            visited.push_back(list.front());
            for (int i = num - 1; i >= 0; i--) {
                push(list.front(), i);
            }
            list.pop();
        }
        cout << "No solution" << endl;
    }
};

int main()
{
    problem b;
    b.bfs();
    return 0;
}


问题 B: 八数码问题–搜索树

题目描述

在3×3的棋盘上,摆有八个棋子,每个棋子上标有1至8的某一数字。棋盘中留有一个空格,空格用0来表示。空格周围的棋子可以移到空格中。
给出一种初始状态S0和目标状态Sg,请找到一种最少步骤的移动方法,实现从初始状态S0到目标状态Sg的转变。
在这里插入图片描述

输入

输入测试次数t
对于每次测试,首先输入一个初始状态S0,一行九个数字,空格用0表示。然后输入一个目标状态Sg,一行九个数字,空格用0表示。

输出

只有一行,该行只有一个数字,表示从初始状态S0到目标状态Sg需要的最少移动次数(测试数据中无特殊无法到达目标状态数据)

样例输入

2
283104765
123804765
283104765
283164705

样例输出

4
1

题解

#include <iostream>
#include <string>
#include <queue>
#include <map>
#include <algorithm>
using namespace std;
vector<string> checked;

void push(vector<string>& v, string str) {
    if (find(checked.begin(), checked.end(), str) == checked.end()) {
        v.push_back(str);
        checked.push_back(str);
    }
}

void pushdata(vector<string>& v, string x) {
    int j = x.find('0');
    string nextx, temp = x;
    switch (j) {
    case 0: {
        temp = x;
        swap(temp[0], temp[1]);
        push(v, temp);
        temp = x;
        swap(temp[0], temp[3]);
        push(v, temp);
        break;
    }
    case 1: {
        temp = x;
        swap(temp[0], temp[1]);
        push(v, temp);
        temp = x;
        swap(temp[1], temp[2]);
        push(v, temp);
        temp = x;
        swap(temp[1], temp[4]);
        push(v, temp);
        break;
    }
    case 2: {
        temp = x;
        swap(temp[2], temp[1]);
        push(v, temp);
        temp = x;
        swap(temp[2], temp[5]);
        push(v, temp);
        break;
    }
    case 3: {
        temp = x;
        swap(temp[3], temp[0]);
        push(v, temp);
        temp = x;
        swap(temp[3], temp[4]);
        push(v, temp);
        temp = x;
        swap(temp[3], temp[6]);
        push(v, temp);
        break;
    }
    case 4: {
        temp = x;
        swap(temp[4], temp[1]);
        push(v, temp);
        temp = x;
        swap(temp[4], temp[3]);
        push(v, temp);
        temp = x;
        swap(temp[4], temp[5]);
        push(v, temp);
        temp = x;
        swap(temp[4], temp[7]);
        push(v, temp);
        break;
    }
    case 5: {
        temp = x;
        swap(temp[5], temp[2]);
        push(v, temp);
        temp = x;
        swap(temp[5], temp[4]);
        push(v, temp);
        temp = x;
        swap(temp[5], temp[8]);
        push(v, temp);
        break;
    }
    case 6: {
        temp = x;
        swap(temp[6], temp[3]);
        push(v, temp);
        temp = x;
        swap(temp[6], temp[7]);
        push(v, temp);
        break;
    }
    case 7: {
        temp = x;
        swap(temp[7], temp[4]);
        push(v, temp);
        temp = x;
        swap(temp[7], temp[6]);
        push(v, temp);
        temp = x;
        swap(temp[7], temp[8]);
        push(v, temp);
        break;
    }
    case 8: {
        temp = x;
        swap(temp[8], temp[5]);
        push(v, temp);
        temp = x;
        swap(temp[8], temp[7]);
        push(v, temp);
        break;
    }
    }
}

int main() {
    int t;
    cin >> t;
    while (t--) {
        string start, end;
        cin >> start >> end;
        checked.clear();
        vector<string>* v = new vector<string>[10];
        v[0].push_back(start);
        checked.push_back(start);
        if (start == end) {
            cout << 0 << endl;
            break;
        }
        for (int i = 1; i < 10; i++) {
            for (string x : v[i - 1]) {
                pushdata(v[i], x);
            }
            if (find(v[i].begin(), v[i].end(), end) != v[i].end()) {
                cout << i << endl;
                break;
            }
        }
    }

    return 0;
}

问题 C: 骑士

题目描述

国际象棋中骑士的走法如图所示。
请计算给定骑士在棋盘上的起点,走到终点所需最少步数。
在这里插入图片描述

输入

每个测试包括一行,为用空格隔开的起点和终点。每个点由字母表示的列+数字表示的行组成。

输出

最少步数

样例输入

e2 e4
a1 b2
b2 c3
a1 h8

样例输出

2
4
2
6

题解

#include <iostream>
#include <string>
#include <queue>
#include <map>
#include <algorithm>
using namespace std;
vector<string> checked;

string tostring(int i, int j) {
    char s1 = i + 'a' - 1, s2 = j + '0';
    string str;
    str.push_back(s1);
    str.push_back(s2);
    return str;
}

bool check(int i_, int j_) {
    if (i_ <= 0 || j_ <= 0 || i_ >= 27 || j_ >= 10)
        return false;
    return true;
}

void push(vector<string>& v, int i_, int j_) {
    if (check(i_, j_)) {
        if (find(checked.begin(), checked.end(), tostring(i_, j_)) == checked.end()) {
            v.push_back(tostring(i_, j_));
            checked.push_back(tostring(i_, j_));
        }
    }
}

void pushdata(vector<string>& v, string x) {
    int i = x[0] - 'a' + 1, j = x[1] - '0';
    int i_, j_;
    i_ = i - 2, j_ = j - 1;
    push(v, i_, j_);
    i_ = i - 2, j_ = j + 1;
    push(v, i_, j_);
    i_ = i - 1, j_ = j - 2;
    push(v, i_, j_);
    i_ = i - 1, j_ = j + 2;
    push(v, i_, j_);
    i_ = i + 1, j_ = j - 2;
    push(v, i_, j_);
    i_ = i + 1, j_ = j + 2;
    push(v, i_, j_);
    i_ = i + 2, j_ = j - 1;
    push(v, i_, j_);
    i_ = i + 2, j_ = j + 1;
    push(v, i_, j_);

}

int main() {
    string start, end;
    while (cin >> start >> end) {
        checked.clear();
        vector<string>* v = new vector<string>[10];
        v[0].push_back(start);
        checked.push_back(start);
        if (start == end) {
            cout << 0 << endl;
            break;
        }
        for (int i = 1; i < 10; i++) {
            for (string x : v[i - 1]) {
                pushdata(v[i], x);
            }
            if (find(v[i].begin(), v[i].end(), end) != v[i].end()) {
                cout << i << endl;
                break;
            }
        }
    }

    return 0;
}

0

评论区