acwing-179. 八数码

发表于 分类于 阅读次数： Waline： 本文字数： 993 阅读时长 ≈ 3 分钟

考点

  • Astar
  • 双向BFS

题解

见思路

思路

先要判断是否有解，思路请参见奇数码问题。

Astar

估价函数设计为所有数字在当前状态中的位置，与目标状态中的位置的曼哈顿距离之和。

因为每次移动只能把一个数字与空格交换位置，至多把一个数字向它在目标状态中的位置接近一步；即使每一步都有意义，不会产生额外开销，从任何一个状态到目标状态的移动步数也不可能小于所有数字当前位置与目标位置的曼哈顿距离之和。

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
#include <bits/stdc++.h>
using namespace std;

// 当前状态到目标状态的理想全局曼哈顿距离
int f(string state) {
  int res = 0;
  for (int i = 0; i < state.length(); ++i) {
    if (state[i] == 'x') continue;
    int t = state[i] - '1';
    res += abs(t / 3 - i / 3) + abs(t % 3 - i % 3);
  }
  return res;
}

bool valid(int x, int y) { return x >= 0 && y >= 0 && x < 3 && y < 3; }

string bfs(string S) {
  int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
  char op[4] = {'u', 'r', 'd', 'l'};
  string T = "12345678x";
  // unordered_map<b, d>
  // b到S的开销为d
  unordered_map<string, int> dist;
  // unordered_map<b, pair<a, c>>
  // b由a通过c操作转换得到
  unordered_map<string, pair<string, char>> prev;
  priority_queue<pair<int, string>, vector<pair<int, string>>> q;
  q.push({-f(S), S});
  while (!q.empty()) {
    string now = q.top().second;
    q.pop();
    if (now == T) break;
    // 找到x的位置
    int x, y;
    for (int i = 0; i < now.length(); ++i) {
      if (now[i] == 'x') {
        x = i / 3, y = i % 3;
        break;
      }
    }
    // 四个方向移动
    string s = now;
    for (int i = 0; i < 4; ++i) {
      int nx = x + dx[i], ny = y + dy[i];
      if (!valid(nx, ny)) continue;
      swap(now[x * 3 + y], now[nx * 3 + ny]);
      // 没被访问过（无穷大）或开销更小，更新
      if (!dist.count(now) || dist[now] > dist[s] + 1) {
        dist[now] = dist[s] + 1;
        prev[now] = {s, op[i]};
        q.push({-(dist[now] + f(now)), now});
      }
      swap(now[x * 3 + y], now[nx * 3 + ny]);
    }
  }
  string path;
  while (T != S) {
    path += prev[T].second;
    T = prev[T].first;
  }
  reverse(path.begin(), path.end());
  return path;
}

int main() {
  char c;
  string str, seq;
  while (cin >> c) {
    str += c;
    if (c != 'x') seq += c;
  }
  // 八数码问题用逆序对数的奇偶性判断是否有解
  int num = 0;
  for (int i = 0; i < seq.length(); ++i) {
    for (int j = 0; j < i; ++j) {
      if (seq[i] < seq[j]) ++num;
    }
  }
  cout << ((num & 1) ? "unsolvable" : bfs(str)) << endl;
  return 0;
}

双向BFS

astar的作法很难想，我本人是用双向BFS码的，唯一的难点就在于保存路径！！！

反向BFS的方向数组要取反；

正向BFS的路径应取反，求正向BFS路径时，我们是从中间状态朝起始状态遍历；

反向BFS的路径不可以取反，求反向BFS路径时，我们是从中间状态朝目标状态遍历。

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
#include <bits/stdc++.h>
using namespace std;
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
// 反向BFS的方向数组取反
char opa[4] = {'u', 'r', 'd', 'l'}, opb[4] = {'d', 'l', 'u', 'r'};
string mid;

bool valid(int x, int y) { return x >= 0 && y >= 0 && x < 3 && y < 3; }

bool extend(queue<string> &aq, unordered_map<string, pair<string, char>> &ap,
            unordered_map<string, bool> &av, unordered_map<string, bool> &bv,
            char op[]) {
  int sz = aq.size();
  while (sz--) {
    string s = aq.front();
    aq.pop();
    if (bv.count(s)) {
      mid = s;
      return true;
    }
    // 找x的位置
    int x, y;
    for (int i = 0; i < s.length(); ++i) {
      if (s[i] == 'x') {
        x = i / 3, y = i % 3;
        break;
      }
    }
    // 四个方向扩展
    string source = s;
    for (int i = 0; i < 4; ++i) {
      int nx = x + dx[i], ny = y + dy[i];
      if (!valid(nx, ny)) continue;
      swap(s[x * 3 + y], s[nx * 3 + ny]);
      if (!av.count(s)) av[s] = 1, ap[s] = {source, op[i]}, aq.push(s);
      swap(s[x * 3 + y], s[nx * 3 + ny]);
    }
  }
  return false;
}

string bfs(string S) {
  string T = "12345678x";
  unordered_map<string, bool> av, bv;
  unordered_map<string, pair<string, char>> ap, bp;
  queue<string> aq, bq;
  aq.push(S), bq.push(T);
  av[S] = 1, bv[T] = 1;
  while (!aq.empty() && !bq.empty()) {
    bool flag = 0;
    flag = aq.size() < bq.size() ? extend(aq, ap, av, bv, opa)
                                 : extend(bq, bp, bv, av, opb);
    if (flag) break;
  }
  string res, tmp = mid;
  while (tmp != S) {
    res += ap[tmp].second;
    tmp = ap[tmp].first;
  }
  reverse(res.begin(), res.end());
  while (mid != T) {
    res += bp[mid].second;
    mid = bp[mid].first;
  }
  return res;
}

int main() {
  char c;
  string str, seq;
  while (cin >> c) {
    str += c;
    if (c != 'x') seq += c;
  }
  // 八数码问题用逆序对数的奇偶性判断是否有解
  int num = 0;
  for (int i = 0; i < seq.length(); ++i) {
    for (int j = 0; j < i; ++j) {
      if (seq[i] < seq[j]) ++num;
    }
  }
  cout << ((num & 1) ? "unsolvable" : bfs(str)) << endl;
  return 0;
}