前言
首先，建议大家读一下原题目，题目的内容这里就不放了，大家可以到这个地址去下载: https://vjudge.net/problem/UVA-12569，有些人可能说英文不太好，那么，也没关系，除了查字典，现在还可以使用这个翻译插件：沉浸式翻译，总之，现在英语语言层面的问题是不会有问题的。
为什么我建议大家读原题目呢？虽然我们大家接触到这个题目可能都是通过刘汝佳的这本《算法竞赛入门经典》才选择去看的，但是，书中给出的描述都是很略的，简单讲一点，题目很重要的输入和输出样例数据，书上一般都是没有的，其他的细节更不必说。大概就这样。
然后，我们来详细研究一下 UVa12569 这道题的思路和解析。
这道题整体的思路是 BFS。然后代码参考(可能有我的微小调整)的是《算法竞赛入门经典-习题与解答》的配套代码，GitHub 地址为：https://github.com/sukhoeing/aoapc-bac2nd-keys。
此外，如果我们想要更多的测试数据，这个 udebug 的网站也是必不可少的：https://www.udebug.com。本题的测试数据地址为：https://www.udebug.com/UVa/12569。
同时，我的代码托管在了这个地址：https://github.com/sonnycalcr/aoapc-homework。
首先，这道题很多人可能觉得简单，我说一下我的观点：对于初学者或者算法初阶的同学来讲，这道题还是有很多值得学习的部分的。
接下来，我挑一些关键的代码讲一下，更详细的解释在代码的注释里面。
注意，在具体看/写代码之前，我们首先要明确一个点，题目中的编号是从 1 开始递增的，而下面我们的程序都是从 0 开始递增的。
Part1
先看数据结构，一个是 Node，
1struct Node {
2 int from, to;
3 Node *next;
4};
Node 是表示路径的链表节点，to 表示的是当前的节点，from 是上一个节点，主要是用来在 State 类型中表示 path，也就是当前的状态是由上一个状态从 from 移动了机器人/石头到 to 而转化过来的。
Part2
再看 State，
1struct State {
2 Node *path; // 路径
3 int g; // 状态压缩，前 4 位(当然是从右往左)表示机器人🤖位置的编号，因为节点数 n 的范围是：4 <= n <= 15，后面 16 位的每一位用来表示位置 i 上是否有石头，比如，(2 + 4) 这个 bit 位为 1，就表示编号为 2 的位置上有石头
4 int len; // 路径长度，到了当前状态已经经历的长度
5 State(int gi = 0, int li = 0, Node *pn = NULL) : g(gi), len(li), path(pn) {}
6 inline bool operator[](size_t i) const { return g & (1 << (i + 4)); } // 位置 i 上是否有石头，前 4 位被机器人占据了，往后的位才能用来表示石头
7 inline void setRock(size_t i, bool val = true) { // 设置位置 i 上是否有石头
8 if (val)
9 g |= 1 << (i + 4); // 位或操作来把第(i + 4)位来置 1
10 else
11 g &= ~(1 << (i + 4)); // 先取反，再用与操作来把第(i + 4)位来置 0
12 }
13 // 机器人的位置操作
14 inline int getP() const { return g & 15; } // 与 1111(二进制) 进行与操作，取出前 4 位的值，也就是机器人的位置
15 inline void setP(int p) { g = ((g >> 4) << 4) | p; } // 设置机器人的位置，这里先右移再左移 4 位清除原有的数据
16};
所谓的 State，就是当前的局面，由以下几个维度的数据构成，
path是路径，上面讲过了，其中保存了上一个状态转变到当前状态是移动了哪一个编号，然后又是移动到了哪一个编号，同时next指向了上一次状态的path。g代表了整体的状态，其中，前 4 位(分别是：0, 1, 2, 3)二进制值作为一个整体可以转化成十进制，表示了当前机器人在哪个编号的位置；然后再往左取 16 位二进制 bit 位，其中每一位都代表了一个编号，比如，0 号位置的 bit 位是 (0 + 4)，也就是第 4 位，如果这一位为 1，则表示树中编号为 0 的位置上有石头，反之则没有，其它的编号依此类推。len表示从最原始的状态来到了当前的状态，一共走了多少步。
理解了上面的几个成员变量，就不难理解之后的几个成员函数了。
Part3
我们再看输出运算符的重载，
1// 一个递归的输出，因为 tryMove 保证了最终到达终点时的状态中的 path 是递归地往前指的
2ostream &operator<<(ostream &os, Node *p) {
3 if (p == NULL)
4 return os;
5 os << p->next << p->from + 1 << " " << p->to + 1 << endl; // 这里要把 from 和 to 分别加 1 来映射成题目中的从 1 开始的序号
6 return os;
7}
这里我们要注意，因为 Node 实际上是用来表示 State 中的 path 的，所以，并且，我们是到了最后成功到达终点时(看代码 109 行)直接打印最终的那个 State 的 path 的，而每一个 path 指向的又是上一个 State 的 path，所以，这个输出重载就达到了输出从初始的状态移动到最终目标的全部路径的目的。
Part4
然后，我们看一下尝试移动机器人或者石头的思路，在这之前，我们先再来看一下全局变量，
1const int MAXN = 16; // 节点的最大数量是 16，根据题目中的条件得来
2vector<int> G[MAXN]; // 图的邻接矩阵表示，题目中简化成了树(无环图)
3MemPool<Node> pool; // 链表节点分配，用 MemPool 比较好管理内存
4// n: 顶点数；m: 障碍物(石头)数量；S: 源，即机器人的起点位置；T: 目标位置
5// O: 每一个石头的位置编号
6// VIS: 表示某个位置是否已经 visited 过了
7int n, m, S, T, O[MAXN], VIS[1 << 19];
这个注释比较清晰了，就不多讲了。然后，让我们进入正题，来看 tryMove 这个函数，
1// 尝试移动在点 from 上的物体(机器人或者石头)
2void tryMove(const State &s, int from, queue<State> &q) {
3 int rp = s.getP(); // 获取当前状态下机器人的位置编号
4 for (auto to : G[from]) {
5 if ((to == rp) || s[to]) // to 和当前状态的机器人位置重合或者 to 的位置上有机器人
6 continue;
7 int ng = s.g;
8 if (from == rp)
9 ng = ((s.g >> 4) << 4) | to; // 把 s.g 的前 4 位置成 to 这个值，也就是移动机器人到 to 的位置
10 else
11 ng ^= (1 << (from + 4)), ng ^= (1 << (to + 4)); // 把 ng 的 from 对应的 bit 位置 0，然后把 to 对应的 bit 位置 1，也就是把石头从 from 位置移动到 to 这个位置
12 if (VIS[ng])
13 continue; // 新的状态已经访问过
14 VIS[ng] = 1; // 标记访问
15 // 这里构建的新 State 的 newNode 的 next 属性指向的是移动前的 State 的 path Node
16 q.push(State(ng, s.len + 1, newNode(s.path, from, to)));
17 }
18}
因为 G 是邻接矩阵，我们可以利用这个特点来进行 for 循环，遍历与 from 顶点所邻接的几个顶点，尝试去移动到这些位置，然后就是一系列的细节处理，看注释比较容易理解。
Part5
下面我们来看最终的核心的代码，
1// bfs
2void solve() {
3 // 定义并初始化原始的状态
4 State s;
5 _for(i, 0, m) s.setRock(O[i]);
6 s.setP(S);
7 queue<State> q;
8 q.push(s);
9 VIS[s.g] = 1; // 标记当前机器人和石头的状态已经被访问过
10 // bfs 一层一层地遍历
11 while (!q.empty()) {
12 const State &st = q.front();
13 int rp = st.getP();
14 if (rp == T) { // 到达目的地，因为是 bfs，所以一旦到达目的地，也就表明是最短路径之一，后面不可能有移动步数更少的结果，最好的情况也是花费和当前一样的步数
15 cout << st.len << endl << st.path;
16 return;
17 }
18 tryMove(st, rp, q); // 尝试移动机器人
19 _for(i, 0, n) if (st[i]) tryMove(st, i, q); // 尝试移动石头
20 q.pop();
21 }
22 cout << "-1" << endl; // 无法到达目的地
23}
这里就是一个纯粹的 bfs，我们定义好了原始的状态之后，然后利用队列这个数据结构一圈一圈地往外进行波纹扩散性地遍历，队列中从前往后存放的分别是第 1 圈、第 2 圈…的数据，而且队列是先进先出(FIFO, First In First Out)，所以，我们可以暴力地遍历所有的情况，并且，可以保证，一旦第一次得到了想要的结果，那么，这个结果就是我们最终想要的结果。
完整的代码和注释
以上就是关键的代码和解释了。其他的东西没什么好讲的。关于数据的输入和处理，上面也没有细讲，直接看注释即可。
下面就是完整的代码和详细的注释：
1#include <cmath>
2#include <cstring>
3#include <iostream>
4#include <queue>
5#include <vector>
6#include <fstream>
7
8#define _for(i, a, b) for (int i = (a); i < (b); ++i)
9
10using namespace std;
11
12int readint() {
13 int x;
14 cin >> x;
15 return x;
16}
17
18template <typename T> struct MemPool {
19 vector<T *> buf;
20 T *createNew() {
21 buf.push_back(new T());
22 return buf.back();
23 }
24
25 void dispose() {
26 for (int i = 0; i < buf.size(); i++)
27 delete buf[i];
28 buf.clear();
29 }
30};
31
32const int MAXN = 16; // 节点的最大数量是 16
33
34struct Node { // 表示路径的链表节点，to 表示的是当前的节点，from 是上一个节点
35 int from, to;
36 Node *next;
37};
38
39struct State {
40 Node *path; // 路径
41 int g; // 状态压缩，前 4 位(当然是从右往左)表示机器人🤖位置的编号，因为节点数 n 的范围是：4 <= n <= 15，后面 16 位的每一位用来表示位置 i 上是否有石头，比如，(2 + 4) 这个 bit 位为 1，就表示编号为 2 的位置上有石头
42 int len; // 路径长度，到了当前状态已经经历的长度
43 State(int gi = 0, int li = 0, Node *pn = NULL) : g(gi), len(li), path(pn) {}
44 inline bool operator[](size_t i) const { return g & (1 << (i + 4)); } // 位置 i 上是否有石头，前 4 位被机器人占据了，往后的位才能用来表示石头
45 inline void setRock(size_t i, bool val = true) { // 设置位置 i 上是否有石头
46 if (val)
47 g |= 1 << (i + 4); // 位或操作来把第(i + 4)位来置 1
48 else
49 g &= ~(1 << (i + 4)); // 先取反，再用与操作来把第(i + 4)位来置 0
50 }
51 // 机器人的位置操作
52 inline int getP() const { return g & 15; } // 与 1111(二进制) 进行与操作，取出前 4 位的值，也就是机器人的位置
53 inline void setP(int p) { g = ((g >> 4) << 4) | p; } // 设置机器人的位置，这里先右移再左移 4 位清除原有的数据
54};
55
56vector<int> G[MAXN]; // 图的邻接矩阵表示，题目中简化成了树(无环图)
57MemPool<Node> pool; // 链表节点分配，用 MemPool 比较好管理内存
58// n: 顶点数；m: 障碍物(石头)数量；S: 源，即机器人的起点位置；T: 目标位置
59// O: 每一个石头的位置编号
60// VIS: 表示某个位置是否已经 visited 过了
61int n, m, S, T, O[MAXN], VIS[1 << 19];
62Node *newNode(Node *next = NULL, int u = -1, int v = -1) {
63 Node *p = pool.createNew();
64 p->next = next, p->from = u, p->to = v;
65 return p;
66}
67
68// 一个递归的输出，因为 tryMove 保证了最终到达终点时的状态中的 path 是递归地往前指的
69ostream &operator<<(ostream &os, Node *p) {
70 if (p == NULL)
71 return os;
72 os << p->next << p->from + 1 << " " << p->to + 1 << endl; // 这里要把 from 和 to 分别加 1 来映射成题目中的从 1 开始的序号
73 return os;
74}
75
76// 尝试移动在点 from 上的物体(机器人或者石头)
77void tryMove(const State &s, int from, queue<State> &q) {
78 int rp = s.getP(); // 获取当前状态下机器人的位置编号
79 for (auto to : G[from]) {
80 if ((to == rp) || s[to]) // to 和当前状态的机器人位置重合或者 to 的位置上有机器人
81 continue;
82 int ng = s.g;
83 if (from == rp)
84 ng = ((s.g >> 4) << 4) | to; // 把 s.g 的前 4 位置成 to 这个值，也就是移动机器人到 to 的位置
85 else
86 ng ^= (1 << (from + 4)), ng ^= (1 << (to + 4)); // 把 ng 的 from 对应的 bit 位置 0，然后把 to 对应的 bit 位置 1，也就是把石头从 from 位置移动到 to 这个位置
87 if (VIS[ng])
88 continue; // 新的状态已经访问过
89 VIS[ng] = 1; // 标记访问
90 // 这里构建的新 State 的 newNode 的 next 属性指向的是移动前的 State 的 path Node
91 q.push(State(ng, s.len + 1, newNode(s.path, from, to)));
92 }
93}
94
95// bfs
96void solve() {
97 // 定义并初始化原始的状态
98 State s;
99 _for(i, 0, m) s.setRock(O[i]);
100 s.setP(S);
101 queue<State> q;
102 q.push(s);
103 VIS[s.g] = 1; // 标记当前机器人和石头的状态已经被访问过
104 // bfs 一层一层地遍历
105 while (!q.empty()) {
106 const State &st = q.front();
107 int rp = st.getP();
108 if (rp == T) { // 到达目的地，因为是 bfs，所以一旦到达目的地，也就表明是最短路径之一，后面不可能有移动步数更少的结果，最好的情况也是花费和当前一样的步数
109 cout << st.len << endl << st.path;
110 return;
111 }
112 tryMove(st, rp, q); // 尝试移动机器人
113 _for(i, 0, n) if (st[i]) tryMove(st, i, q); // 尝试移动石头
114 q.pop();
115 }
116 cout << "-1" << endl; // 无法到达目的地
117}
118
119int main() {
120 // 重定向标准输入到文件
121 string relativePathToCurrentCppFile = "./data/UVa12569/input1.txt";
122 // relativePathToCurrentCppFile = "./data/UVa12569/input2.txt";
123 // 因为我们是在根目录下执行编译出来的可执行文件的
124 ifstream inputFile("./ch07" + relativePathToCurrentCppFile.substr(1, relativePathToCurrentCppFile.size() - 1));
125 if (!inputFile.is_open()) {
126 cerr << "Failed to open input data file." << endl;
127 return 2;
128 }
129 streambuf *cinbuf = cin.rdbuf(); // save original buf
130 cin.rdbuf(inputFile.rdbuf());
131
132 int K = readint(); // 读取 case 的数量，为了和 case 关键字区分，一般用 Kase 或者 K 来表示 case
133 for (int t = 1; t <= K; t++) {
134 memset(VIS, 0, sizeof(VIS)); // 初始化置 0
135 cin >> n >> m >> S >> T; // 读入 n m S T
136 --S; // 程序用到的编号要减 1
137 --T; // 同上
138 cout << "Case " << t << ": ";
139 _for(i, 0, m) O[i] = readint() - 1; // 读入石头的编号，编号是从给的数据减 1 而得来
140 _for(i, 0, n) G[i].clear(); // 清除之前的数据
141
142 // 构建邻接矩阵
143 _for(i, 0, n - 1) { // 读入 n - 1 条边
144 int u = readint() - 1, v = readint() - 1; // 每一个顶点的编号都要减 1
145 G[u].push_back(v);
146 G[v].push_back(u);
147 }
148
149 solve();
150 pool.dispose(); // 释放内存
151 cout << endl;
152 }
153
154 // 恢复标准输入
155 cin.rdbuf(cinbuf);
156 return 0;
157}
纯净的代码
由于上面的代码我为了自己测试方便进行标准输入流重定向的处理，是不能直接提交的，所以，我在下面提供一份纯净的可以用于提交验证的代码，这里同时去除了所有的注释，因为中文字符似乎不被接受，
1#include <cmath>
2#include <cstring>
3#include <iostream>
4#include <queue>
5#include <vector>
6
7#define _for(i, a, b) for (int i = (a); i < (b); ++i)
8
9using namespace std;
10
11int readint() {
12 int x;
13 cin >> x;
14 return x;
15}
16
17template <typename T> struct MemPool {
18 vector<T *> buf;
19 T *createNew() {
20 buf.push_back(new T());
21 return buf.back();
22 }
23
24 void dispose() {
25 for (int i = 0; i < buf.size(); i++)
26 delete buf[i];
27 buf.clear();
28 }
29};
30
31const int MAXN = 16;
32
33struct Node {
34 int from, to;
35 Node *next;
36};
37
38struct State {
39 Node *path;
40 int g;
41 int len;
42 State(int gi = 0, int li = 0, Node *pn = NULL) : g(gi), len(li), path(pn) {}
43 inline bool operator[](size_t i) const { return g & (1 << (i + 4)); }
44 inline void setRock(size_t i, bool val = true) {
45 if (val)
46 g |= 1 << (i + 4);
47 else
48 g &= ~(1 << (i + 4));
49 }
50
51 inline int getP() const { return g & 15; }
52 inline void setP(int p) { g = ((g >> 4) << 4) | p; }
53};
54
55vector<int> G[MAXN];
56MemPool<Node> pool;
57
58int n, m, S, T, O[MAXN], VIS[1 << 19];
59Node *newNode(Node *next = NULL, int u = -1, int v = -1) {
60 Node *p = pool.createNew();
61 p->next = next, p->from = u, p->to = v;
62 return p;
63}
64
65ostream &operator<<(ostream &os, Node *p) {
66 if (p == NULL)
67 return os;
68 os << p->next << p->from + 1 << " " << p->to + 1 << endl;
69 return os;
70}
71
72void tryMove(const State &s, int from, queue<State> &q) {
73 int rp = s.getP();
74 for (auto to : G[from]) {
75 if ((to == rp) || s[to])
76 continue;
77 int ng = s.g;
78 if (from == rp)
79 ng = ((s.g >> 4) << 4) | to;
80 else
81 ng ^= (1 << (from + 4)), ng ^= (1 << (to + 4));
82 if (VIS[ng])
83 continue;
84 VIS[ng] = 1;
85
86 q.push(State(ng, s.len + 1, newNode(s.path, from, to)));
87 }
88}
89
90void solve() {
91
92 State s;
93 _for(i, 0, m) s.setRock(O[i]);
94 s.setP(S);
95 queue<State> q;
96 q.push(s);
97 VIS[s.g] = 1;
98
99 while (!q.empty()) {
100 const State &st = q.front();
101 int rp = st.getP();
102 if (rp == T) {
103 cout << st.len << endl << st.path;
104 return;
105 }
106 tryMove(st, rp, q);
107 _for(i, 0, n) if (st[i]) tryMove(st, i, q);
108 q.pop();
109 }
110 cout << "-1" << endl;
111}
112
113int main() {
114 int K = readint();
115 for (int t = 1; t <= K; t++) {
116 memset(VIS, 0, sizeof(VIS));
117 cin >> n >> m >> S >> T;
118 --S;
119 --T;
120 cout << "Case " << t << ": ";
121 _for(i, 0, m) O[i] = readint() - 1;
122 _for(i, 0, n) G[i].clear();
123
124 _for(i, 0, n - 1) {
125 int u = readint() - 1, v = readint() - 1;
126 G[u].push_back(v);
127 G[v].push_back(u);
128 }
129
130 solve();
131 pool.dispose();
132 cout << endl;
133 }
134
135 return 0;
136}
当然，这个代码也是可以在我的 GitHub 仓库中找到的。
参考
1、《算法竞赛入门经典》第二版
2、https://github.com/sukhoeing/aoapc-bac2nd-keys