今天更新一篇,直奔主题。
题意:
有一棵n(4<=n<=15)个结点的树,其中一个结点有一个机器人,还有一些结点有石头。每步可以把一个机器人或石头移到一个相邻的节点。任何情况下一个结点里不能有两个东西(石头或机器人)。输入每个石头的位置和机器人的起点和终点,求最小步数的方案。如果有多解,可以输出任意解。
建议看原题。
思路:
由于(4<=n<=15)以及求最小步数的方案,所以我们可以采用bfs的方法去做,对于路径寻找问题,自然需要对不同的状态进行记录,根据n很小我们可以采用状态压缩(二进制)进行表示。
我们采用STL的set或者hash进行查找重复,但是set太慢了,也许之前做的题对时间要求不高,于是使用了set发现超时,试了试hash发现快了很多2000ms左右
下面是代码:
set超时代码
// UVa 12569 // bfs+状态压缩+剪枝 #include <cstdio> #include <cstring> #include <vector> #include <set> using namespace std; typedef long long LL; struct Node { LL tree; int robpos, f, t, root, dep; Node(LL tree=0, int robpos=0, int f=0, int t=0, int root=0, int dep=0) : tree(tree), robpos(robpos), f(f), t(t), root(root), dep(dep) {} }; int n, m, s, t, G[20][20]; int kase; int l, r; vector<Node> v; set<pair<LL, int> > Set; void Move(Node& u1, int i, int j, int root) { if (u1.robpos == i) u1.robpos = j; u1.tree ^= (1<<i); u1.tree |= (1<<j); u1.root = root; u1.f = i; u1.t = j; } bool try_to_insert(Node& u, int i, int j) { LL tree = u.tree; int robpos = u.robpos; if (robpos == i) robpos = j; tree ^= (1<<i); tree |= (1<<j); if (!Set.count(make_pair(tree, robpos))) { Set.insert(make_pair(tree, robpos)); return true; } return false; } void Print(int cur) { if (cur != 0) { Print(v[cur].root); printf("%d %d\n", v[cur].f, v[cur].t); } } void bfs(Node& start) { v.clear(); Set.clear(); Set.insert(make_pair(start.tree, start.robpos)); v.push_back(start); l = 0; r = 1; while (l < r) { Node u = v[l]; l++; if (u.robpos == t) { printf("Case %d: %d\n", ++kase, u.dep); Print(l-1); puts(""); return; } for (int i = 1; i <= n; ++i) if (u.tree&(1<<i)) for (int j = 1; j <= n; ++j) if (G[i][j] && (u.tree&(1<<j)) == 0 && try_to_insert(u, i, j)) { Node u1; memcpy(&u1, &u, sizeof(u1)); u1.dep = u.dep + 1; Move(u1, i, j, l-1); v.push_back(u1); r++; } } printf("Case %d: -1\n\n", ++kase); } int main() { int T; scanf("%d", &T); while (T--) { scanf("%d%d%d%d", &n, &m, &s, &t); Node start(0, s, 0, 0, -1, 0); start.tree |= (1<<s); for (int i = 0; i < m; ++i) { int stone; scanf("%d", &stone); start.tree |= (1<<stone); } memset(G, 0, sizeof(G)); for (int i = 0; i < n-1; ++i) { int u, v; scanf("%d%d", &u, &v); G[u][v] = G[v][u] = 1; } bfs(start); } return 0; }
hash快速代码
// UVa 12569 // bfs+状态压缩+剪枝(不用set用hash) #include <cstdio> #include <cstring> #include <vector> using namespace std; struct Node { int tree, robpos, f, t, root, dep; Node(int tree=0, int robpos=0, int f=0, int t=0, int root=0, int dep=0) : tree(tree), robpos(robpos), f(f), t(t), root(root), dep(dep) {} }; int n, m, s, t, G[20][20]; int kase; int l, r; vector<Node> v; void Move(Node& u1, int i, int j, int root) { if (u1.robpos == i) u1.robpos = j; u1.tree ^= (1<<i); u1.tree |= (1<<j); u1.root = root; u1.f = i; u1.t = j; } const int hashsize = 131072; // 2 ^ 16 int Head[hashsize+10], Next[100003]; // just try void init_lookup_table() { memset(Head, -1, sizeof(Head)); } int try_to_insert(Node& u, int i, int j, int pos) { int tree = u.tree, robpos = u.robpos; if (robpos == i) robpos = j; tree ^= (1<<i); tree |= (1<<j); int u1 = Head[tree]; while (u1 != -1) { if (v[u1].robpos == robpos) return 0; u1 = Next[u1]; } Next[pos] = Head[tree]; Head[tree] = pos; return 1; } void Print(int cur) { if (cur != 0) { Print(v[cur].root); printf("%d %d\n", v[cur].f, v[cur].t); } } void bfs(Node& start) { init_lookup_table(); v.clear(); v.push_back(start); l = 0; r = 1; while (l < r) { Node u = v[l]; l++; if (u.robpos == t) { printf("Case %d: %d\n", ++kase, u.dep); Print(l-1); puts(""); return; } for (int i = 1; i <= n; ++i) if (u.tree&(1<<i)) for (int j = 1; j <= n; ++j) if (G[i][j] && (u.tree&(1<<j)) == 0 && try_to_insert(u, i, j, r)) { Node u1; memcpy(&u1, &u, sizeof(u1)); u1.dep = u.dep + 1; Move(u1, i, j, l-1); v.push_back(u1); r++; } } printf("Case %d: -1\n\n", ++kase); } int main() { int T; scanf("%d", &T); while (T--) { scanf("%d%d%d%d", &n, &m, &s, &t); Node start(0, s, 0, 0, -1, 0); start.tree |= (1<<s); for (int i = 0; i < m; ++i) { int stone; scanf("%d", &stone); start.tree |= (1<<stone); } memset(G, 0, sizeof(G)); for (int i = 0; i < n-1; ++i) { int u, v; scanf("%d%d", &u, &v); G[u][v] = G[v][u] = 1; } bfs(start); } return 0; }
就这样,不懂的地方问我,我会及时回复的。