目錄
- 問題 A: 過河問題--搜尋樹
- 問題 B: 八數位問題--搜尋樹
- 問題 C: 騎士
問題 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的轉變。
![]()
【資料結構】搜尋樹問題 A: 過河問題–搜尋樹問題 B: 八數位問題–搜尋樹問題 C: 騎士
輸入
輸入測試次數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: 騎士
題目描述
國際象棋中騎士的走法如圖所示。
請計算給定騎士在棋盤上的起點,走到終點所需最少步數。
![]()
【資料結構】搜尋樹問題 A: 過河問題–搜尋樹問題 B: 八數位問題–搜尋樹問題 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;
}