首页 > 代码库 > UVA - 1533 Moving Pegs
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; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。