#include <iostream> #include <queue> #include <vector> #include <cstring> #include <algorithm> using namespace std; // 状态结构体：左岸神父、左岸恶魔、船位置(0左/1右)、步数、路径 struct State { int p, d, boat; int step; vector<pair<int, int>> path; // 每一步：(上船神父数, 上船恶魔数) }; int n, m; bool vis[111][111][2]; // 访问标记 n<=20 够用 void output(int x , int y) { if(x == 0) if(y == 1) cout << y << " devil.\n" ; else cout << y << " devils.\n" ; else if(y == 0) if(x == 1) cout << x << " father.\n" ; else cout << x << " fathers.\n" ; else { if(x == 1) cout << x << " father and\n" ; else cout << x << " fathers and\n" ; if(y == 1) cout << y << " devil.\n" ; else cout << y << " devils.\n" ; } } // 检查单个位置是否合法 bool isSafe(int p, int d) { if (p < 0 || d < 0 || p > n || d > n) return false; // 该岸无神父，一定安全 if (p == 0) return true; return p >= d; } // 船上人员合法校验 bool boatSafe(int bp, int bd) { if (bp + bd < 1 || bp + bd > m) return false; // 人数1~m if (bp == 0) return true; return bp >= bd; } // 比较函数：按题目规则排序（优先选人数多→神父多，字典序最大） bool cmp(const pair<int, int>& a, const pair<int, int>& b) { int sumA = a.first + a.second; int sumB = b.first + b.second; if (sumA != sumB) return sumA > sumB; return a.first > b.first; } int bfs() { memset(vis, 0, sizeof(vis)); queue<State> q; // 初始状态：左岸n神父n恶魔，船在左，步数0 State start = {n, n, 0, 0, {}}; q.push(start); vis[n][n][0] = true; while (!q.empty()) { State cur = q.front(); q.pop(); // 到达终点：左岸0神父0恶魔，船在右岸 if (cur.p == 0 && cur.d == 0 && cur.boat == 1) { // 输出步数 + 路径 cout << cur.step << endl; for (auto& x : cur.path) { output(x.first , x.second) ; } return cur.step; } vector<pair<int, int>> nextBoat; // 所有合法乘船方案 if (cur.boat == 0) { // 船在左岸：载人去右岸 // 枚举船上神父bp、恶魔bd for (int bp = 0; bp <= cur.p; bp++) { for (int bd = 0; bd <= cur.d; bd++) { if (!boatSafe(bp, bd)) continue; int np = cur.p - bp; int nd = cur.d - bd; // 检查两岸都安全 if (isSafe(np, nd) && isSafe(n - np, n - nd)) { nextBoat.emplace_back(bp, bd); } } } } else { // 船在右岸：载人返回左岸 int r_p = n - cur.p; // 右岸神父 int r_d = n - cur.d; // 右岸恶魔 for (int bp = 0; bp <= r_p; bp++) { for (int bd = 0; bd <= r_d; bd++) { if (!boatSafe(bp, bd)) continue; int np = cur.p + bp; int nd = cur.d + bd; if (isSafe(np, nd) && isSafe(n - np, n - nd)) { nextBoat.emplace_back(bp, bd); } } } } // 按题目规则排序：人数多→神父多（字典序最大） sort(nextBoat.begin(), nextBoat.end(), cmp); // 遍历所有合法乘船方案，扩展状态 for (auto& bd : nextBoat) { int bp = bd.first; int dd = bd.second; int np, nd, nboat; if (cur.boat == 0) { np = cur.p - bp; nd = cur.d - dd; nboat = 1; } else { np = cur.p + bp; nd = cur.d + dd; nboat = 0; } if (!vis[np][nd][nboat]) { vis[np][nd][nboat] = true; State nxt = cur; nxt.p = np; nxt.d = nd; nxt.boat = nboat; nxt.step += 1; nxt.path.push_back({bp, dd}); q.push(nxt); } } } // 队列为空，无解 return -1; } int main() { cin >> n >> m; int res = bfs(); if (res == -1) { cout << -1 << endl; } return 0; }