题目描述

有三个野人三个道士，他们在何的右岸，现有一艘只能容纳两个人的小船，因为野人比较野蛮，如果河一侧野人的数量大于道士的数量，野人就会攻击道士，问如何安全的过河。输出任意一种方案。

问题分析

这道题目可以通过搜索来实现，广搜和深搜均可，在这里为了锻炼使用广搜的代码能力，笔者决定用广搜来解答这道题目。

为了进行广搜我们需要创建一个三元组$(x, (y, z))$，分别代表着河右岸道士的人数，野人的人数，船在左侧还是在右侧，其中记 $1$ 为船在右侧，记 $0$ 为船在左侧。就可以通过两种情况进行分类讨论。

当 $z=1$ 时，有以下几种情况：
– 两个道士到达左岸
– 一个道士一个野人到达左岸
– 一个道士到达左岸
– 一个野人到达左岸
– 两个野人到达左岸。

当 $z=2$ 时的情况与上文相近，只是从左岸到达右岸。

分析完毕后，我们可以得到以下的转移数组：

int dx[10] =  {-1, -1, -2, 0, 0, 1, 1, 2, 0, 0};
int dy[10] =  {-1, 0, 0, -1, -2, 1, 0, 0, 2, 1};

其中 $0-5$ 号元素代表着船在右岸的情况，剩余的元素代表船在左岸的情况。在转移的时候要判断状态的合法性，切记如果某一时刻道士的人数为 $0$ 野人是无法攻击道士的。

因为题目要求需要输出合法的方案，故在广搜的时候我们需要通过链表记录一下这个状态的上一个转台，最后从最后的状态开始，倒序输出。倒序输出可以通过栈来实现，这里不做过多的讲解。

参考代码

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

int dx[10] =  {-1, -1, -2, 0, 0, 1, 1, 2, 0, 0};
int dy[10] =  {-1, 0, 0, -1, -2, 1, 0, 0, 2, 1};
int used[5][5][5];
int n = 3;
map<pair<int, pair<int, int>>, pair<int, pair<int, int>>> ans;

void out() {
    stack<pair<int, pair<int, int>>> tmp;
    pair<int, pair<int, int>> it =  make_pair(0, make_pair(0, 0)), ed = make_pair(3, make_pair(3, 1));
    do{
        tmp.push(it);
        it = ans[it];
    }while(it != ed);
//  cout << it.first << " " << it.second.first << " " << it.second.second << "\n";
    tmp.push(it);
    while(!tmp.empty()) cout << tmp.top().first << " " << tmp.top().second.first << " " << tmp.top().second.second << "\n", tmp.pop();
    exit(0);
}

void bfs() {
    queue<pair<int, pair<int, int>>> q;
    
    q.push(make_pair(3, make_pair(3, 1)));
    while(!q.empty()) {
        if(q.front() == make_pair(0, make_pair(0, 0)))  {
            out();
            return ;
        }
        int x = q.front().first, y = q.front().second.first; 
        if(q.front().second.second) {
            for(int i = 0; i < 5; i++) {
                int nx = x + dx[i], ny = y + dy[i];
                if((nx < ny && nx != 0) || (n - nx < n - ny && nx != 3)|| used[nx][ny][0] != 0|| nx < 0 || ny < 0|| nx > n || ny > n) continue;
                used[nx][ny][0] = 1;
                q.push(make_pair(nx, make_pair(ny, 0)));
                ans[make_pair(nx, make_pair(ny, 0))] = make_pair(x, make_pair(y, 1));
            }
        }
        else {
            for(int i = 5; i < 10; i++) {
                int nx = x + dx[i], ny = y + dy[i];
                if((nx < ny && nx != 0) || (n - nx < n - ny && nx != 3)||used[nx][ny][1] != 0|| nx < 0 || ny < 0|| nx > n || ny > n) continue;
                used[nx][ny][1] = 1;
                q.push(make_pair(nx, make_pair(ny, 1)));
                ans[make_pair(nx, make_pair(ny, 1))] = make_pair(x, make_pair(y, 0));
            }
        }
        q.pop();
    }
} 



int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
//  freopen("AKIOI.in", "r", stdin);
//  freopen("AKIOI.out", "w", stdout);
    bfs();
    return 0;
}