UVA 1604 立体八数码问题——编码解码+哈希+dfs

UVA 1604 立体八数码问题——编码解码+哈希+dfs

双广度优先搜索+状态压缩+hash去重

这题关键是一点一点把上面三个模块写好，我的模块仅供参考：

1.开头到分割线是状态压缩，这里我用了9位10进制编码压缩了状态图，用了一个二维数组维护了各种旋转状态，每个人的写法各异，代码仅供参考

2.两条分割线之间是hash表，采用了邻接表的形式实现了完美哈希表，其中ok是是否插入元素的开关，毕竟判断路径相遇时不能插入元素

3.后面的部分是双广度有限搜索，其中init是各种元素的初始化，dfs是将256个末状态入队（因为你只知道末状态的颜色，而不知道具体状态），然后是双搜，双搜的时候注意控制层数，因为末状态一开始就比较多，所以他的扩展层数应该小，这里正向21层反向9层效果最佳

4这题真的写了好久，细节很多，建议大家写的时候一定要分好模块，不然改起来很麻烦

#include #include #include #include #include using namespace std;const int rot[7][4] = { {0, 0, 0, 0}, {2, 2, 6, 6}, {1, 1, 3, 3}, {4, 4, 2, 2}, {3, 3, 5, 5}, {6, 6, 4, 4}, {5, 5, 1, 1}};const int state_color[] = {0, 1, 2, 3, 1, 2 ,3};const int dx[] = {1, -1, 0, 0};const int dy[] = {0, 0, 1, -1};int G[5][5];int cod(int ctrl) { int temp = 0; if (ctrl) { for (int i = 1; i <= 3; i++) { for (int j = 1; j <= 3; j++) { temp = temp * 10 + G[i][j]; } } } else { for (int i = 1; i <= 3; i++) { for (int j = 1; j <= 3; j++) { temp = temp * 10 + state_color[ G[i][j] ]; } } } return temp;}void decode(int temp) { int cnt = 100000000; for (int i = 1; i <= 3; i++) { for (int j = 1; j <= 3; j++) { G[i][j] = temp / cnt; temp = temp % cnt; cnt /= 10; } }}void change(int x, int y, int xx, int yy, int p) { G[x][y] = rot[G[xx][yy]][p]; G[xx][yy] = 0;}//********************************************const int hashsize = 1000000 + 7;struct HASH { int data; vector link;}haxi1[hashsize], haxi2[hashsize];void hash_init() { for (int i = 0; i < hashsize; i++) { haxi1[i].data = 0; haxi1[i].link.clear(); } for (int i = 0; i < hashsize; i++) { haxi2[i].data = 0; haxi2[i].link.clear(); }}bool ha_sh(int x, int who, int ok) { int y = x % hashsize; if (who == 1) { if (haxi1[y].data == 0) { if (ok) haxi1[y].data = x; return false; } if (haxi1[y].data == x) return true; if (haxi1[y].data != x) { int len = haxi1[y].link.size(); for (int i = 0; i < len; i++) { if (haxi1[y].link[i] == x) return true; } if(ok) haxi1[y].link.push_back(x); return false; } } else if (who == 2) { if (haxi2[y].data == 0) { if (ok) haxi2[y].data = x; return false; } if (haxi2[y].data == x) return true; if (haxi2[y].data != x) { int len = haxi2[y].link.size(); for (int i = 0; i < len; i++) { if (haxi2[y].link[i] == x) return true; } if(ok) haxi2[y].link.push_back(x); return false; } }}//*********************************************8int m, n, mr, nr, goal, ans;struct Node { int x, y, step, passwd;}node;queue q1, q2;const int mp[4][2] = { {0, 0}, {1, 4}, {2, 5}, {3, 6}};void dfs(int x, int y) { if (x > 3) { node.passwd = cod(1); if ( !ha_sh(node.passwd, 2, 1) ) { q2.push(node); } return; } int temp = G[x][y]; if (temp == 0) { if (y + 1 <= 3) dfs(x, y + 1); else dfs(x + 1, 1); } else { for (int i = 0; i < 2; i++) { G[x][y] = mp[temp][i]; if (y + 1 <= 3) dfs(x, y + 1); else dfs(x + 1, 1); G[x][y] = temp; } }}bool init() { hash_init(); while (!q1.empty()) q1.pop(); while (!q2.empty()) q2.pop(); goal = 0, ans = 0; for (int i = 1; i <= 3; i++) { for (int j = 1; j <= 3; j++) { char c; cin >> c; int temp; if (c == 'E') { mr = i, nr = j; temp = 0; } else if (c == 'W') temp = 1; else if (c == 'R') temp = 2; else if (c == 'B') temp = 3; goal = goal * 10 + temp; } } for (int i = 1; i <= 3; i++) { for (int j = 1; j <= 3; j++) { G[i][j] = 1; } } G[m][n] = 0; if (cod(0) == goal) return false; node.x = m, node.y = n, node.step = 0, node.passwd = cod(1); ha_sh(node.passwd, 1, 1); q1.push(node); decode(goal); node.x = mr, node.y = nr, node.step = 0; dfs(1, 1); return true;}void bfs() { int cnt1 = 0, cnt2 = 0; while (true) { bool edge = true; while (!q1.empty() && q1.front().step <= cnt1) { edge = false; node = q1.front(); q1.pop(); int x = node.x, y = node.y, step = node.step, passwd = node.passwd, pw; if (ha_sh(passwd, 2, 0)) { ans = step + cnt2; return; } for (int i = 0; i < 4; i++) { int xx = x + dx[i], yy = y + dy[i]; if (1 <= xx && xx <= 3 && 1 <= yy && yy <= 3 && step < 21) { decode(passwd); change(x, y, xx, yy, i); pw = cod(1); if (!ha_sh(pw, 1, 1)) { node.x = xx, node.y = yy, node.step = step + 1, node.passwd = pw; q1.push(node); } } } } if (cnt1 < 21) cnt1++; while (!q2.empty() && q2.front().step <= cnt2) { edge = false; node = q2.front(); q2.pop(); int x = node.x, y = node.y, step = node.step, passwd = node.passwd, pw; if (ha_sh(passwd, 1, 0)) { ans = step + cnt1; return; } for (int i = 0; i < 4; i++) { int xx = x + dx[i], yy = y + dy[i]; if (1 <= xx && xx <= 3 && 1 <= yy && yy <= 3 && step < 9) { decode(passwd); change(x, y, xx, yy, i); pw = cod(1); if (!ha_sh(pw, 2, 1)) { node.x = xx, node.y = yy, node.step = step + 1, node.passwd = pw; q2.push(node); } } } } if (cnt2 < 9) cnt2++; if (edge) { ans = -1; return; } }}int main(){ while (scanf("%d %d", &n, &m) == 2 && n && m) { if (init()) bfs(); printf("%d\n", ans); } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。