给出一个地图, ?是1~9表示蛇头到蛇尾, @表示?, 问最少多少步能吃到?. 此外, ?不能重叠, 但如果?头过来的瞬间尾巴走了, 那也不算重叠.
其实这个题就是普通的BFS的变形, 另外要注意一些细节.
Ⅰ 结构体中保存当前?的状态, 普通BFS只有坐标和步数, 但是一条?还要保存它的身子位置, 以防下一步撞到自己身上. 现在用状压表示下一个关节位于上个关节的相对位置, 这样就能很容易地获得?的每个关节的位置. 更重要的, 在?的爬行中, 只要将这个二进制数进行位运算, 再稍加修改, 就能得到?的下个状态.
Ⅱ ?不能撞到自己, 即代表: 蛇头的新位置不能在蛇身的旧状态的任何一个(不是蛇尾的)位置. 另外, ?没有身子(长度为1)不需要考虑碰撞问题; ?长为2的蛇头不能在蛇尾走的瞬间占据蛇尾的位置, ##12@##不能变为##21@#.
Ⅲ 在我的图中, x轴是向下的, y轴是向右的. 因为n是行数, m是列数, x轴正方向代表行增加的方向, y轴正方向代表列增加的方向.
以后一定要注意, 这样图的x和y轴是这样的?.做这个题的时候, 这个毒瘤的坐标系给我带来了巨大的困扰, 我以为是正常的坐标系, 然后错了好久.
以后一定要注意, 这样图的x和y轴是这样的?.
Ⅳ 当蛇头移动到新位置时, 头到第二关节的相对位移是蛇头移动的反方向, 所以要把方向取反, 再放入状压中! 这个也wa了好久.
Ⅴ不能标记vis数组, 因为可能需要把蛇尾撤出来蛇头再进去, 像这样:
... ... .1. #2# #@#如果标记了1位置不能再走, 那就再也吃不到苹果了.
Ⅵ 状压的状态在写之前一定要想好, 怎么写(从左往右? 几位表示一个状态?)能让转移时和使用状态时的写法简洁不繁琐.
例如, 在本题中, 完全可以反过来, 高位存储蛇尾状态, 低位存储靠近蛇头一端的状态, 这样转移的时候, 只需要将前面的状态左移, 低位放入新的关节即可, 对于高位, 我们用蛇身长度限制就好了, 超过限制的高位就是没用的状态. 此外, 我们还要考虑我们利用这个状态的时候, 这样的写法会不会导致我们用这个状态的时候很麻烦. 对于这个题, 我们只在检查"是否撞到自己"用到状态, 所以不论如何存储都不会影响写法的复杂程度.
而我在写的时候, 高位存了最近的状态, 低位存蛇尾的状态. 这样就导致我必须右移状态, 再在最前面的位加入新的状态.
虽然这些问题看起来不大, 但是凑在一起真的非常棘手, 希望以后能多注意以上几点, 在写代码之前考虑到使用时是否方便, 会不会很容易写bug, 选择逻辑清晰的方式.
#include<bits/stdc++.h> #define enter puts("") using namespace std; char mp[15][15]; int to[4][2] = {0, 1, 0, -1, 1, 0, -1, 0}; int n, m; struct node { int x, y; } head, app; struct node2 { int x, y; unsigned bits; int step; } now, nex; void BinaryRecursion(int n) {// 递归输出二进制 int a; a = n % 2; n = n >> 1; if (n == 0); else BinaryRecursion(n); cout << a; } int len; void getS(int nowX, int nowY, int nxt, unsigned nowBits) { if (nowX != 0 && mp[nowX - 1][nowY] == '0' + nxt) getS(nowX - 1, nowY, nxt + 1, (nowBits << 1u) << 1u);//00 else if (nowY != 0 && mp[nowX][nowY - 1] == '0' + nxt) getS(nowX, nowY - 1, nxt + 1, ((nowBits << 1u) << 1u) + 1u);//01 else if (nowX < n && mp[nowX + 1][nowY] == '0' + nxt) getS(nowX + 1, nowY, nxt + 1, ((nowBits << 1u) + 1u) << 1u);//10 else if (nowY < m && mp[nowX][nowY + 1] == '0' + nxt) getS(nowX, nowY + 1, nxt + 1, (((nowBits << 1u) + 1u) << 1u) + 1u);//11 else { // BinaryRecursion(nowBits); len = nxt - 1; now.x = head.x, now.y = head.y, now.bits = nowBits; return; } } int vis[15][15]; bool hit(int x, int y, int bfx, int bfy, unsigned bits) { if (x < 0 || y < 0 || x >= n || y >= m)return true; if (mp[x][y] == '#')return true; set<pii> ocu; int nowX = bfx, nowY = bfy; stack<pii> s; int cnt = 0; while (cnt < len - 1) {//去掉头长 unsigned t2 = bits & 1u;//y bits >>= 1u; unsigned t1 = bits & 1u;//x bits >>= 1u; s.push({t1, t2}); cnt++; } if (s.empty())return false;//没有尾巴撞个吉尔 unsigned tot; (s.size() == 1) ? (tot = s.size()) : (tot = s.size() - 1); while (tot) {//撞尾巴不算撞 但是如果只有两节还是要撞啊 tot--; pii tmp = s.top(); if (tmp.first == 1 && tmp.second == 1)nowY++; else if (tmp.first == 1 && tmp.second == 0)nowX++; else if (tmp.first == 0 && tmp.second == 1)nowY--; else if (tmp.first == 0 && tmp.second == 0)nowX--; ocu.insert({nowX, nowY}); s.pop(); } if (ocu.count({x, y}))return true; return false;//没撞 } int bfs() { queue<node2> q; q.push(now); vis[now.x][now.y] = 1; while (!q.empty()) { if (now.step > 2000) { return -1; } now = q.front(); q.pop(); vis[now.x][now.y] = 0; if (mp[now.x][now.y] == '@') { return now.step; } for (int i = 0; i < 4; i++) { nex.x = now.x + to[i][0], nex.y = now.y + to[i][1], nex.step = now.step + 1, nex.bits = now.bits >> 2u; if (len != 1)nex.bits += (((i == 1 || i == 3) ? 1u : 0u)) << ((unsigned) (len - 1) * 2u - 1u); if (len != 1)nex.bits += (((i == 0 || i == 1) ? 1u : 0u)) << ((unsigned) (len - 1) * 2u - 2u); if (hit(nex.x, nex.y, now.x, now.y, now.bits))continue; if (vis[nex.x][nex.y])continue; q.push(nex); vis[nex.x][nex.y] = 1; } } return -1; } void init() { n = read(), m = read(); for (int i = 0; i < n; ++i) { scanf("%s", mp[i]); for (int j = 0; j < m; ++j) { if (mp[i][j] == '1') { head.x = i, head.y = j; } else if (mp[i][j] == '@') { app.x = i, app.y = j; } } } getS(head.x, head.y, 2, 0u); write(bfs()); enter; } int main() { init(); return 0; }
