首页 > 代码库 > UVALive 2520 Holedox Moving（BFS+状态压缩）
UVALive 2520 Holedox Moving（BFS+状态压缩）
这个题目在比赛的时候我们是没有做出来的，但是听到他们说进制哈希的时候，感觉真的是挺高端的，于是赛后开始补题，本着我的习惯在看题解之前自己再试着写一遍，我当时存储状态的方法是string + map，我用string将蛇的各个位置都存下来，用map记录这个状态有没有出现过，当时是过了题目中给的样例，我就开始担心STL会不会超时，后来发现想多了，这个方法WA了，至于为什么，我还没明白，或许是状态的处理错误。总之我自己也觉得这个状态有点不靠谱。。于是开始换用题解的方式。发现所谓的进制哈希，其实就是状态压缩，我们的方向一共有4个，数组下标为0,1,2,3.二进制表示00,01,10,11.
发现每一个方向都占用了两位，蛇身的长度（不包含蛇头）最大是7，所以方向状态最多有(1<<14)个，就可以使用vis[x][y][state]表示蛇头的位置和相对位置的状态压缩数值，在这里需要注意几个问题，vis为了节省空间和时间使用bool型的，state存储状态的时候让靠近蛇头的位置存储在低位。这样做的原因就是容易得到蛇移动以后的下一个状态，让它左移两位就可以。
我自己也敲出了代码，但是出现了迷之bug，两个样例都没有过，所以我在别人的代码上加了注释（我的改对了估计就跟他的一模一样了），这是原博客地址，代码及注释如下：
#include <iostream>#include <cstring>#include <cstdio>#include <queue>using namespace std;const int MAX_S = (1 << 14) + 100;const int MAX_N = 20 + 2;const int INF = (1 << 29);struct State{ int x, y, dis, s; State(int x = 0, int y = 0, int dis = 0, int s = 0) : x(x), y(y), dis(dis), s(s) {};};struct POS{ int x,y;};POS pos[MAX_N];int N, M, res, L;int vis[MAX_N][MAX_N][MAX_S];int fx[4] = {-1, 0, 1, 0};int fy[4] = {0, 1, 0, -1};bool _map[MAX_N][MAX_N];queue <State> Q;int get_start(){ int dir, dx, dy, s = 0; for(int i = L - 1; i > 0; i--)///记录i如何走到i+1，便于回溯 { dx = pos[i].x - pos[i - 1].x, dy = pos[i].y - pos[i - 1].y; if(dx == 0 && dy == 1) dir = 1; else if(dx == 0 && dy == -1) dir = 3; else if(dx == -1 && dy == 0) dir = 0; else if(dx == 1 && dy == 0) dir = 2; s = s << 2; s = s | dir; } return s;}int get_next_state(int i, int s){ int dir; int k = (1 << ((L - 1) << 1)) - 1;///让（l-1）*2都是1，更高位为0 int dx = 0, dy = 0; dx = dx - fx[i], dy = dy - fy[i];///这里不要忘记将方向取反 if(dx == 0 && dy == 1) dir = 1; else if(dx == 0 && dy == -1) dir = 3; else if(dx == -1 && dy == 0) dir = 0; else if(dx == 1 && dy == 0) dir = 2; s = s << 2; s = s | dir; s = s & k; /// 去除高位部分 return s;}bool judge_code(int x, int y, int pre_x, int pre_y, int s)///判断会不会咬到自己{ int dir; for(int i = 0; i < L - 1; i++) { dir = 3; dir = dir & s; s = s >> 2; if(x == pre_x + fx[dir] && y == pre_y + fy[dir]) return false; pre_x = pre_x + fx[dir], pre_y = pre_y + fy[dir]; } return true;}void BFS(){ State a; int dx, dy, s; while(!Q.empty()) { a = Q.front(); Q.pop(); for(int i = 0; i < 4; i++) { dx = a.x + fx[i], dy = a.y + fy[i]; s = get_next_state(i, a.s); if(dx > 0 && dy > 0 && dx <= N && dy <= M && !vis[dx][dy][s] && !_map[dx][dy] && judge_code(dx, dy, a.x, a.y, a.s)) { if(dx == 1 && dy == 1) { res = a.dis + 1; return ; } vis[dx][dy][s] = 1; Q.push(State(dx, dy, a.dis + 1, s)); } } }}int main(){ int s = 0, _case = 0; State _start; while(scanf("%d%d%d", &N, &M, &L), N + M + L) { res = INF; memset(_map, 0 , sizeof(_map)); memset(vis, 0 , sizeof(vis)); for(int i = 0; i < L; i++) scanf("%d%d", &pos[i].x, &pos[i].y); int K, u, v; scanf("%d", &K); for(int i = 0; i < K; i++) { scanf("%d%d", &u, &v); _map[u][v] = 1; } if(pos[0].x == 1 && pos[0].y == 1) { printf("Case %d: 0\n", ++_case); continue; } s = get_start(); Q.push(State(pos[0].x, pos[0].y, 0, s)); vis[pos[0].x][pos[0].y][s] = 1; BFS(); if(res == INF) printf("Case %d: -1\n", ++_case); else printf("Case %d: %d\n", ++_case, res); while(!Q.empty()) Q.pop(); } return 0;}
UVALive 2520 Holedox Moving（BFS+状态压缩）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。