本文主要是介绍UVA - 1533 Moving Pegs，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题意：首先给你空闲的位置，可以跳过几个来吃掉几个，求最短的吃完所有的，且最后一个回到开始指定的位置
思路：BFS+HASH判重，对于每个位置有六个方向，当然有的是不能走的，加上map的判重就可以了
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <set>
#include <queue>
using namespace std;
const int MAXN = 16;int next[15][6] = {{-1, -1, -1, -1, 2, 3}, {-1, 1, -1, 3, 4, 5}, {1, -1, 2, -1, 5, 6}, {-1, 2, -1, 5, 7, 8}, {2, 3, 4, 6, 8, 9}, {3, -1, 5, -1, 9, 10}, {-1, 4, -1, 8, 11, 12}, {4, 5, 7, 9, 12, 13}, {5, 6, 8, 10, 13, 14}, {6, -1, 9, -1, 14, 15}, {-1, 7, -1, 12, -1, -1}, {7, 8, 11, 13, -1, -1}, {8, 9, 12, 14, -1, -1}, {9, 10, 13, 15, -1, -1}, {10, -1, 14, -1, -1, -1}
};struct Statue {int st;int num;int way[2][MAXN];int cnt;Statue(int _st = (1<<16) - 1, int _num = 15) {st = _st;num = _num;cnt = 0;}
};
queue<Statue> q;
set<int> s;
int n;int bfs() {s.clear();while (!q.empty()) q.pop();q.push(Statue(((1<<16)-1)^(1<<(n-1)), 14));while (!q.empty()) {Statue tmp = q.front();q.pop();for (int i = 0; i < 15; i++) { if ((tmp.st>>i)&1) { for (int j = 0; j < 6; j++) { if (next[i][j] != -1 && ((tmp.st>>(next[i][j]-1))&1)) { int tt = i;Statue cur = tmp;while (tt >= 0 && (cur.st>>tt)&1) {cur.st -= (1<<tt);cur.num--;tt = next[tt][j] - 1;}cur.num++;if (tt < 0) continue;cur.st |= (1<<tt);if (!s.count(cur.st)) {s.insert(cur.st);cur.way[0][cur.cnt] = i + 1;cur.way[1][cur.cnt] = tt + 1;cur.cnt++;if (cur.num == 1 && (cur.st>>(n-1))&1) {printf("%d\n%d %d", cur.cnt, cur.way[0][0], cur.way[1][0]);for (int i = 1; i < cur.cnt; i++) {printf(" %d %d", cur.way[0][i], cur.way[1][i]);}puts("");return 0;}q.push(cur);}}}}}}printf("IMPOSSIBLE\n");return 0;
}int main() {int t;scanf("%d", &t);while (t--) {scanf("%d", &n);bfs();}return 0;
}这篇关于UVA - 1533 Moving Pegs的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
