P5507. 机关

发表于 分类于 阅读次数： Waline： 本文字数： 1.1k 阅读时长 ≈ 4 分钟

考点

  • Astar
  • 双向BFS

题解

见思路。

思路

尽管数据范围已经告诉你，但是依旧不能使用IDAstar，搜索树过大会超时。

这题纯纯是在考位运算的奇技淫巧...原题给的1 - 4下标与状态不好编程，统一降低成0 - 3

假设当前状态为s，那么正扭的下个状态是(s + 1) & 3，反扭（实际上就是扭三次）的下个状态是(s + 3) & 3

如果要取下标为idx的按钮状态，那么应该是(s >> (idx << 1)) & 3

假设当前下标为x，状态为sx，新状态为nsx：

  • 先要从s中清除x的旧状态，应该为s -= (sx << (x << 1))，

  • 再添加新状态s |= (nsx << (x << 1))

双向BFS

双向BFS有几个坑，坑了我一整天：

  • 非常非常非常非常非常卡常数时间，除了输入和输出一律改为scanf/printf外，

    记录状态不能用哈希表，要用普通数组；记录路径也不能用哈希表，要用vector代替

  • 假设当前是x下标的按钮，状态为sx：

    正扭影响到的按钮下标为nxt[x][sx]

    反扭影响到的按钮下标为nxt[x][(sx + 3) & 3]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1 << 24;
int st, ed, mid, nxt[14][6], out[maxn];
bool av[maxn], bv[maxn];
// ap[f]<pair<g, h>，f状态是由g状态选了h旋钮转换得来
vector<pair<int, int>> ap(maxn), bp(maxn);

int extend(queue<pair<int, int>> &aq, queue<pair<int, int>> &bq, bool av[],
           bool bv[], vector<pair<int, int>> &ap, int dir) {
  int sz = aq.size();
  while (sz--) {
    int state = aq.front().first, step = aq.front().second;
    aq.pop();
    // x：当前旋钮，y：受牵引的旋钮，sx：x的状态，sy：y的状态
    // nsx：x的下一次状态，nsy：y的下一次状态，ns：全局下一次状态
    int x, y, sx, sy, nsx, nsy, ns;
    for (int x = 0; x < 12; ++x) {
      if (dir == 1) {
        // 正向
        sx = (state >> (x << 1)) & 3, y = nxt[x][sx];
        sy = (state >> (y << 1)) & 3;
        nsx = (sx + 1) & 3, nsy = (sy + 1) & 3;
      } else {
        // 反向，注意受牵引的按钮不是sx，是(sx + 3) & 3
        sx = (state >> (x << 1)) & 3, y = nxt[x][(sx + 3) & 3];
        sy = (state >> (y << 1)) & 3;
        nsx = (sx + 3) & 3, nsy = (sy + 3) & 3;
      }
      ns = state;
      ns -= (sx << (x << 1)), ns |= (nsx << (x << 1));
      ns -= (sy << (y << 1)), ns |= (nsy << (y << 1));
      if (av[ns]) continue;
      ap[ns] = {state, x + 1};
      if (bv[ns]) {
        mid = ns;
        return 1 + step + bq.front().second;
      }
      av[ns] = 1;
      aq.push({ns, step + 1});
    }
  }
  return -1;
}

void bfs() {
  // queue<pair<f, g>>到达f状态走了g步
  queue<pair<int, int>> aq, bq;
  aq.push({st, 0}), bq.push({0, 0});
  av[st] = 1, bv[0] = 1;
  int res;
  while (!aq.empty() && !bq.empty()) {
    if (aq.size() <= bq.size()) {
      res = extend(aq, bq, av, bv, ap, 1);
    } else {
      res = extend(bq, aq, bv, av, bp, 2);
    }
    if (res != -1) break;
  }
  printf("%d\n", res);
  // 正向搜索部分，从中间态到初始态倒序输出路径
  int idx = 0, tmp = mid;
  while (tmp != st) {
    out[++idx] = ap[tmp].second;
    tmp = ap[tmp].first;
  }
  while (idx) printf("%d ", out[idx--]);
  // 反向搜索部分，从中间态到终态正序输出路径
  while (mid != 0) {
    out[++idx] = bp[mid].second;
    mid = bp[mid].first;
  }
  for (int i = 1; i <= idx; ++i) printf("%d ", out[i]);
}

int main() {
  for (int button, i = 0; i < 12; ++i) {
    scanf("%d", &button);
    st |= (button - 1) << (i << 1);
    for (int j = 0; j < 4; ++j) {
      scanf("%d", &nxt[i][j]);
      nxt[i][j] -= 1;
    }
  }
  bfs();
  return 0;
}

Astar

如果当前某个按钮的状态为2，那么扭到0还需要走2步

统计所有按钮需要的步数之和tot，那么估价函数就可以设为向上取整(tot / 2)，

因为每次还会带动另一个按钮转动，所以除2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1 << 24;
int st, ed, nxt[14][6], d[maxn], out[maxn];
// p[a], pair<b, c>：当前a状态是由b状态选了c转换
vector<pair<int, int>> p(maxn);

int f(int s) {
  int res = 0;
  for (int i = 0; i < 12; ++i) {
    if ((s >> (i << 1)) & 3) res += 4 - ((s >> (i << 1)) & 3);
  }
  // 记得向上取整
  return (res + 2 - 1) / 2;
}

void bfs() {
  memset(d, 0x3f, sizeof(d));
  // pair<a, b>
  // a：初始态到当前状态的最小开销+未来最小开销，b：当前状态
  priority_queue<pair<int, int>, vector<pair<int, int>>> q;
  d[st] = 0;
  q.push({-f(st), st});
  while (!q.empty()) {
    int state = q.top().second;
    q.pop();
    if (state == ed) {
      printf("%d\n", d[ed]);
      break;
    }
    for (int x = 0; x < 12; ++x) {
      int sx = (state >> (x << 1)) & 3, nsx = (sx + 1) & 3;
      int y = nxt[x][sx], sy = (state >> (y << 1)) & 3, nsy = (sy + 1) & 3;
      int ns = state;
      ns -= (sx << (x << 1)), ns |= (nsx << (x << 1));
      ns -= (sy << (y << 1)), ns |= (nsy << (y << 1));
      if (d[ns] == 0x3f3f3f3f || d[ns] > d[state] + 1) {
        d[ns] = d[state] + 1;
        p[ns] = {state, x + 1};
        q.push({-(d[ns] + f(ns)), ns});
      }
    }
  }
  // 倒序输出路径
  int idx = 0;
  while (ed != st) {
    out[++idx] = p[ed].second;
    ed = p[ed].first;
  }
  while (idx) printf("%d ", out[idx--]);
}

int main() {
  for (int button, i = 0; i < 12; ++i) {
    scanf("%d", &button);
    st |= (button - 1) << (i << 1);
    for (int j = 0; j < 4; ++j) {
      scanf("%d", &nxt[i][j]);
      nxt[i][j] -= 1;
    }
  }
  bfs();
  return 0;
}