题目跳转

POJ1077 Eight

题目大意

经典八数码问题，无需赘述。

本人思路

BFS - 康托展开 - A*

• 上下左右移动的操作直接自己想好二维的形态，直接在一维中实现
• 将每个没有在自己位置的棋子与自己的应在的位置的曼哈顿距离之和作为估价函数f
• 康托展开进行哈希

我的其他思路：

1. 用map代替康托展开来哈希

   • 不加A* TLE
   • 加了A* 比康托展开慢
   • 康托展开的复杂度为O(n^2)，而map的时间复杂度为O(nlogn)，但是不难发现，用map实现时，会多次调用map中时间复杂度为O(logn)的函数，导致常数较大，而本题n很小，所以导致map比康托展开慢
   • 代码会附在正解后面
2. 本题只用康托展开也会TLE，但代码不再展示。

CODE

/*************************\
*不加逆序对特判无解 2552 ms*
*       加了       76 ms  *
\*************************/

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

using namespace std;

const int N = 362880;
const int factory[10] = {1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880};

struct Node
{
  int val;
  string st, path;

  bool operator<(const Node &o) const
  {
    return val > o.val;
  }
};
bool vis[N];
string str;
priority_queue<Node> heap;

bool Cantor(string str, int n = 9)
{
  int CantorIdx = 0;
  for (int i = 0; i < n; i++)
  {
    int cnt = 0;
    for (int j = i + 1; j < n; j++)
      if (str[i] > str[j])
        cnt++;
    CantorIdx += cnt * factory[n - i - 1];
  }
  if (!vis[CantorIdx])
  {
    vis[CantorIdx] = true;
    return false;
  }
  return true;
}
int f(string str, int n = 9)
{
  int res = 0;
  for (int i = 0; i < n; i++)
    if (str[i] != 'x')
    {
      int t = str[i] - '1';
      int oa = t / 3, ob = t % 3;
      int na = i / 3, nb = i % 3;
      res += abs(oa - na) + abs(ob - nb);
    }
  return res;
}
void bfs()
{
  heap.push((Node){f(str), str, ""});
  Cantor(str);
  while (heap.size())
  {
    Node t = heap.top(), tmp;
    heap.pop();
    // cout << t.val << " " << t.st << " " << t.path << endl;
    if (t.st == "12345678x")
    {
      cout << t.path << '\n';
      return;
    }
    int pos;
    for (int i = 0; i < 9; i++)
      if (t.st[i] == 'x')
        pos = i;
    tmp = t;
    if (pos >= 3) // up
    {
      swap(tmp.st[pos], tmp.st[pos - 3]);
      if (!Cantor(tmp.st))
      {
        tmp.path += 'u';
        tmp.val = f(tmp.st) + tmp.path.size();
        heap.push(tmp);
      }
    }
    tmp = t;
    if (pos < 6) // down
    {
      swap(tmp.st[pos], tmp.st[pos + 3]);
      if (!Cantor(tmp.st))
      {
        tmp.path += 'd';
        tmp.val = f(tmp.st) + tmp.path.size();
        heap.push(tmp);
      }
    }
    tmp = t;
    if (pos % 3 != 0) // left
    {
      swap(tmp.st[pos], tmp.st[pos - 1]);
      if (!Cantor(tmp.st))
      {
        tmp.path += 'l';
        tmp.val = f(tmp.st) + tmp.path.size();
        heap.push(tmp);
      }
    }
    tmp = t;
    if (pos % 3 != 2) // right
    {
      swap(tmp.st[pos], tmp.st[pos + 1]);
      if (!Cantor(tmp.st))
      {
        tmp.path += 'r';
        tmp.val = f(tmp.st) + tmp.path.size();
        heap.push(tmp);
      }
    }
  }
  cout << "unsolvable" << '\n';
  return;
}

int main()
{
  ios::sync_with_stdio(0);
  cin.tie(0);
  // freopen("i.txt", "r", stdin);
  // freopen("o.txt", "w", stdout);
  for (int i = 0; i < 9; i++)
  {
    char ch;
    cin >> ch;
    str += ch;
  }
  // spj 无解
  int cnt = 0;
  for (int i = 0; i < str.size(); i++)
    for (int j = i + 1; j < str.size(); j++)
      if (str[i] > str[j] && str[i] != 'x' && str[j] != 'x')
        cnt++;
  if (cnt & 1)
    cout << "unsolvable" << '\n';
  else
    bfs();
  return 0;
}

只用map实现 - TLE

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

using namespace std;

struct Node
{
  string st, path;
};

string str;
queue<Node> q;
map<string, int> strInt;

void bfs()
{
  q.push((Node){str, ""});
  strInt[str] = 0;
  while (q.size())
  {
    Node t = q.front(), tmp;
    q.pop();
    if (t.st == "12345678x")
    {
      cout << t.path << '\n';
      return;
    }
    int pos;
    for (int i = 0; i < 9; i++)
      if (t.st[i] == 'x')
        pos = i;
    tmp = t;
    if (pos >= 3) // up
    {
      swap(tmp.st[pos], tmp.st[pos - 3]);
      if (strInt.count(tmp.st) == 0)
      {
        tmp.path += 'u';
        strInt[tmp.st] = strInt[t.st] + 1;
        q.push(tmp);
      }
    }
    tmp = t;
    if (pos < 6) // down
    {
      swap(tmp.st[pos], tmp.st[pos + 3]);
      if (strInt.count(tmp.st) == 0)
      {
        tmp.path += 'd';
        strInt[tmp.st] = strInt[t.st] + 1;
        q.push(tmp);
      }
    }
    tmp = t;
    if (pos % 3 != 0) // left
    {
      swap(tmp.st[pos], tmp.st[pos - 1]);
      if (strInt.count(tmp.st) == 0)
      {
        tmp.path += 'l';
        strInt[tmp.st] = strInt[t.st] + 1;
        q.push(tmp);
      }
    }
    tmp = t;
    if (pos % 3 != 2) // right
    {
      swap(tmp.st[pos], tmp.st[pos + 1]);
      if (strInt.count(tmp.st) == 0)
      {
        tmp.path += 'r';
        strInt[tmp.st] = strInt[t.st] + 1;
        q.push(tmp);
      }
    }
  }
  cout << "unsolvable" << '\n';
  return;
}

int main()
{
  ios::sync_with_stdio(0);
  cin.tie(0);
  // freopen("i.txt", "r", stdin);
  // freopen("o.txt", "w", stdout);
  for (int i = 0; i < 9; i++)
  {
    char ch;
    cin >> ch;
    str += ch;
  }
  bfs();
  return 0;
}
// map TLE 怀疑是常数比较大
// unordered_map POJ不支持，acwing是过了，且先上下快点