【算法竞赛 - 搜索】Eight II

Livinfly

发布于 2022-10-26 16:14:02

21500

代码可运行

文章被收录于专栏：LivinflyLivinfly

运行总次数：0

代码可运行

题目跳转

HDOJ3567

题目大意

经典八数码问题，和POJ1077相比，指定了末位置，并且要求输出最小字典序。

思路

DBFS - 康托展开 - 状态压缩

DBFS
- 考虑到确定了起点和终点，并且可以互相到达，采用双向广搜。
康托展开
- 对八数码状态的绝配Hash
状态压缩
- 采用四进制来存储路径，经暴力可得，步数最大30左右。

我的原始思路TLE：

map做`状态`和`路径`的映射，同时充当标记的作用。
代码会贴在文末

其他说明

并不是正搜，只按字典序小，倒搜只按字典序大就对，需要再把状态搜完比较！

该处有一个数据生成器

只是缺少了始末状态一致的数据，导致我血压高了几小时。（和标程对拍没有问题，交上去就WA）

CODE

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <queue>

using namespace std;

typedef long long LL;
struct Node
{
  char str[12];
  int pos, hx, step; // X的位置，哈希值，步数
  LL path; // 0123 - dlru
  int is_ordered; //是否有序
};
// 预处理阶乘
const int factory[10] = {1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880};

int ans_step;
LL ans; // 路径的数字形式
LL power4[40]; // 35
char ans_path[40], dir[5] = "dlru";
int d[2][362890]; // dist 1代表正序，0代表倒叙，下同
LL road[2][362890]; // 存储字典序最小的路径
queue<Node> q;
void prev_calc() // 预处理4的n次方
{
  LL t = 1; // LL!
  for (int i = 0; i < 35; i++, t *= 4)
    power4[i] = t;
}
void init() // 初始化
{
  while (q.size())
    q.pop();
  memset(d, -1, sizeof d);
  memset(road, 0, sizeof road);
  ans_step = ans = -1;
  return;
}
int cantor(char ch[], int n = 9) // 康托展开
{
  int Idx = 0, cnt;
  for (int i = 0; i < n; i++)
  {
    cnt = 0;
    for (int j = i + 1; j < n; j++)
      if (ch[i] > ch[j])
        cnt++;
    Idx += cnt * factory[n - i - 1];
  }
  return Idx;
}
// 其实必要性不大的函数
Node mk_Node(char ch[], int pos, int step, LL path, int is_ordered) 
{
  if (pos == -1)
  {
    for (int i = 0; i < 9; i++)
      if (ch[i] == 'X')
      {
        pos = i;
        break;
      }
  }

  Node t = (Node){{}, pos, cantor(ch), step, path, is_ordered};
  memcpy(t.str, ch, 9);
  return t;
}
void check_nstatus(Node t, Node &nt, int type)
{
  if (d[nt.is_ordered][nt.hx] == -1) // 未访问过
  {
    d[nt.is_ordered][nt.hx] = t.step + 1; // 更新最小步数
    if (nt.is_ordered) // 生成新路径
      nt.path = nt.path * 4 + type;
    else
      nt.path = (3 - type) * power4[nt.step - 1] + nt.path;
    road[nt.is_ordered][nt.hx] = nt.path;
    // 剪枝 - 因为第一次相遇就是最小步数，尽可能让他们的步数相近
    if (ans == -1 || nt.step * 2 <= ans_step) 
      q.push(nt);
  }
  else // 访问过 - 更新字典序
  {
    if (t.step + 1 > d[nt.is_ordered][nt.hx]) // 步数比之前到达过的大
      return;
    else
      d[nt.is_ordered][nt.hx] = t.step + 1; // 更新最小步数
    if (nt.is_ordered) // 生成新路径
      nt.path = nt.path * 4 + type;
    else
      nt.path = (3 - type) * power4[nt.step - 1] + nt.path;
    if (road[nt.is_ordered][nt.hx] > nt.path) // 字典序小
    {
      road[nt.is_ordered][nt.hx] = nt.path;
      // 剪枝 - 因为第一次相遇就是最小步数，尽可能让他们的步数相近
      if (ans == -1 || nt.step * 2 <= ans_step)
        q.push(nt);
    }
  }
  // 相遇
  if (d[nt.is_ordered ^ 1][nt.hx] != -1 && (ans == -1 || ans_step == nt.step + d[nt.is_ordered ^ 1][nt.hx]))
  {
    ans_step = nt.step + d[nt.is_ordered ^ 1][nt.hx];
    LL tans; // 临时变量
    if (nt.is_ordered)
      tans = nt.path * power4[d[0][nt.hx]] + road[0][nt.hx];
    else
      tans = road[1][nt.hx] * power4[d[0][nt.hx]] + nt.path;
    if (ans == -1 || tans < ans)
      ans = tans;
  }
}
void update_nstatus(Node t, int type) // 生成新状态
{
  // dlru
  Node nt = t;
  switch (type)
  {
  case 0:
    if (nt.pos < 6)
    {
      swap(nt.str[nt.pos], nt.str[nt.pos + 3]);
      nt.pos += 3;
      nt.step++;
      nt.hx = cantor(nt.str);
      check_nstatus(t, nt, type);
    }
    break;
  case 1:
    if (nt.pos % 3)
    {
      swap(nt.str[nt.pos], nt.str[nt.pos - 1]);
      nt.pos--;
      nt.step++;
      nt.hx = cantor(nt.str);
      check_nstatus(t, nt, type);
    }
    break;
  case 2:
    if (nt.pos % 3 != 2)
    {
      swap(nt.str[nt.pos], nt.str[nt.pos + 1]);
      nt.pos++;
      nt.step++;
      nt.hx = cantor(nt.str);
      check_nstatus(t, nt, type);
    }
    break;
  case 3:
    if (nt.pos >= 3)
    {
      swap(nt.str[nt.pos], nt.str[nt.pos - 3]);
      nt.pos -= 3;
      nt.step++;
      nt.hx = cantor(nt.str);
      check_nstatus(t, nt, type);
    }
    break;
  }
}
void dbfs(char A[], char Z[])
{
  Node a = mk_Node(A, -1, 0, 0, 1), b = mk_Node(Z, -1, 0, 0, 0);
  q.push(a), q.push(b);
  d[1][a.hx] = d[0][b.hx] = 0;
  road[1][a.hx] = road[0][b.hx] = 0;
  if (a.hx == b.hx)
  {
    ans_step = 0;
    ans = 0;
    return;
  }

  while (q.size())
  {
    Node t = q.front();
    q.pop();
    for (int i = 0; i < 4; i++)
      update_nstatus(t, i);
  }
}
void trans_path()
{
  for (int i = ans_step - 1; i >= 0; i--)
    ans_path[ans_step - 1 - i] = dir[(ans / power4[i]) % 4LL];
  ans_path[ans_step] = '\0'; // 重置，不然会使得上次对char*的更改对下次输出有影响。
}

main()
{
  // freopen("i.txt", "r", stdin);
  // freopen("o.txt", "w", stdout);
  prev_calc();
  int T;
  scanf("%d", &T);
  for (int C = 1; C <= T; C++)
  {
    init();
    char A[12], Z[12];
    scanf("%s\n%s", A, Z);
    dbfs(A, Z);
    trans_path(); // 数字路径转化为字符路径
    printf("Case %d: %d\n%s\n", C, ans_step, ans_path);
  }
  return 0;
}

map朴素写法 - TLE

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <queue>
#include <unordered_map>

using namespace std;

string ans;
char ch[5] = "dlru";
queue<string> q[2];
unordered_map<string, string> mp[2];

void init()
{
  for (int i = 0; i < 2; i++)
  {
    mp[i].clear();
    while (q[i].size())
      q[i].pop();
  }
  ans = "n";
}
string get_nstatus(string str, int pos, int type)
{
  switch (type)
  {
  // down
  case 0:
    if (pos < 6)
      swap(str[pos], str[pos + 3]);
    else
      str = "n";
    break;
  // left
  case 1:
    if (pos % 3 != 0)
      swap(str[pos], str[pos - 1]);
    else
      str = "n";
    break;
  // right
  case 2:
    if (pos % 3 != 2)
      swap(str[pos], str[pos + 1]);
    else
      str = "n";
    break;
  // up
  case 3:
    if (pos >= 3)
      swap(str[pos], str[pos - 3]);
    else
      str = "n";
    break;
  }
  return str;
}
void update_nstatus(queue<string> &q, unordered_map<string, string> &mp1, unordered_map<string, string> &mp2, string t, int pos, int i, bool is_ordered)
{
  string nt = get_nstatus(t, pos, i);
  if (nt != "n" && (!mp1.count(nt) || mp1[t].size() + 1 <= mp1[nt].size())) // 是小于等于啊，等于可以带来字典序的优化！！！！
  {
    if (is_ordered && (!mp1.count(nt) || mp1[t] + ch[i] < mp1[nt])) // 要判断没有 或者 字典序更小
    {
      mp1[nt] = mp1[t] + ch[i];
      if (mp2.count(nt))
      {
        string res = mp1[nt] + mp2[nt];
        if (ans == "n" || (res.size() == ans.size() && res < ans))
          ans = res;
      }
    }
    else if (!is_ordered && (!mp1.count(nt) || ch[3 - i] + mp1[t] < mp1[nt]))
    {
      mp1[nt] = ch[3 - i] + mp1[t];
      if (mp2.count(nt))
      {
        string res = mp2[nt] + mp1[nt];
        if (ans == "n" || (res.size() == ans.size() && res < ans))
          ans = res;
      }
    }
    if (ans != "n" && mp1[nt].size() * 2 > ans.size())
      return;
    q.push(nt);
  }
}
void expand(queue<string> &q, unordered_map<string, string> &mp1, unordered_map<string, string> &mp2, bool is_ordered)
{
  string t = q.front();
  q.pop();
  int pos;
  for (int i = 0; i < 9; i++)
    if (t[i] == 'X')
    {
      pos = i;
      break;
    }
  // dlru
  for (int i = 3; i >= 0; i--)
    update_nstatus(q, mp1, mp2, t, pos, i, is_ordered);
}
void dbfs(string A, string Z)
{
  mp[0][A] = "", mp[1][Z] = "";
  q[0].push(A), q[1].push(Z);
  while (q[0].size() && q[1].size())
  {
    if (q[0].size() < q[1].size())
      expand(q[0], mp[0], mp[1], true);
    else
      expand(q[1], mp[1], mp[0], false);
  }
  //    for(auto x: mp[0])
  //        cout << x.second.size() << endl;
  for (int i = 0; i < 2; i++)
  {
    while (q[i].size())
      expand(q[i], mp[i], mp[1 - i], !i);
  }
}

int main()
{
  // ios::sync_with_stdio(0);
  // cin.tie(0);
  //    freopen("i.txt", "r", stdin);
  // freopen("o.txt", "w", stdout);
  int T;
  scanf("%d", &T);
  for (int Case0 = 1; Case0 <= T; Case0++)
  {
    init();
    string A, Z;
    cin >> A >> Z;
    dbfs(A, Z);
    printf("Case %d: %d\n", Case0, ans.size());
    cout << ans << '\n';
  }
  return 0;
}

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2022年08月12日，如有侵权请联系 cloudcommunity@tencent.com 删除

hash