基本思路就是Bfs：
本题的一个关键就是如何判段状态重复。
1.如果将状态用一个int型数组表示，即假设为int state[17]，state[0]代表机器人的位置，从1到M从小到大表示障碍物的位置。那么如果直接用STL中的set是会超时的，但如果自己建立一个hash方法，像这样：
int getKey(State& s) {
long long v = 0;
for(int i=0; i<=M; ++i ) {
v = v * 10 + s[i];
}
return v % hashSize;
}
是可以避免超时的。
2. 除了上面这种，还有一种方法是用二进制法，因为有15个位置，除了robot，每个位置的状态只有 "有"或"无"，可以分别用1或0表示，那么就是15位的二进制，如
00000 00000 00001 可以表示位置0存在一个障碍物， 转化为int型整数即为 1
11111 00000 11111 可以表示位置0～4， 10～14各存在一个障碍物，转化为int型整数即为31775
那么所有障碍物的状态可以在0～2^15-1的范围内表示出来，另外单独考虑robot的位置，可以用一个bool数组，如 bool vis[32767][15]表示
每次移动障碍物时，先确定移动的起始位置（二进制为1的位置），再确定目标位置（二进制为0且与robot不重合的位置）。
同样机器人移动也是类似的道理。
因为采用了位运算，而且判重方法比上一种相对来得简单，所以速度要比上一种方法快一点。
PS：做这题时，刚开始采用了STL的set方法，结果超时。之后采用了自建hash表的方法，过了，但时间处于5000ms这个级别。后来观察别人的代码，才发现别人采用了二进制的方法(点击查看)，自己才恍然大悟，原理还可以这么做！！！于是自己琢磨了一下，写了一下，并且AC，发现速度大增，马上处于1000ms的级别。
#include <bits/stdc++.h> using namespace std; const int MAXN = (1 << 15) + 50;
bool vis[MAXN][15+2];
struct Node{
int robot, ob, step;
};
typedef pair<int, int> Move; // from first to second
Node q[MAXN*17]; // queue
Move move[MAXN*17];
int movePath[MAXN*17]; // the step before rear is movePath[rear]
vector <int> link[17]; // link table
int n, m, s, target;
int start; void Read() {
cin >> n >> m >> s >> target;
start = 0;
s --;
target --;
int tmp;
for(int i=0; i<m; ++i) {
cin >> tmp;
start = start | (1 << (tmp - 1)); // add ob at position tmp-1
}
for(int i=0; i<n; ++ i) {
link[i].clear();
}
int x, y;
for(int i=0; i<n-1; ++i) {
cin >> x >> y;
link[x-1].push_back(y-1);
link[y-1].push_back(x-1);
}
} // print path
void Print(int rear) {
vector<Move> v;
while(rear) {
v.push_back(move[rear]);
rear = movePath[rear];
}
vector<Move>::iterator it;
for(it = v.end()-1; it>=v.begin(); it--) {
// +1 !!!
cout << it->first + 1 << " " << it->second + 1 << endl;
}
} void Bfs() {
int front = 0, rear = 1;
q[front].ob = start;
q[front].robot = s;
q[front].step = 0;
memset(vis, false, sizeof(vis));
vis[q[front].ob][q[front].robot] = true;
while(front < rear) {
Node& t = q[front];
if(t.robot == target) {
cout << t.step << endl;
Print(front);
return ;
}
for(int i=0; i<n; ++i) { // move i
if((t.ob & (1 << i)) || i == t.robot) {
// there is an ob or a robot at the position
for(size_t j=0; j<link[i].size(); ++ j) {
int nextNode = link[i][j];
if(nextNode == t.robot || ((1<<nextNode) & t.ob)!=0 ) {
// there exists an ob or a robot at the next position
continue;
}
Node next = t;
if(i == t.robot) {
next.robot = nextNode;
} else {
// move from i to nextNode
next.ob = next.ob - (1 << i);
next.ob = next.ob + (1 << nextNode);
}
next.step = t.step + 1;
if(!vis[next.ob][next.robot]) {
vis[next.ob][next.robot] = true;
move[rear].first = i; // from
move[rear].second = nextNode; // next
movePath[rear] = front; // the former step
q[rear ++] = next; // push into the queue
}
}
}
}
++ front;
}
cout << -1 << endl;
} int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int T, Case = 0;
cin >> T;
while(T --) {
Read();
cout << "Case " << (++Case) << ": ";
Bfs();
}
return 0;
}