[C++知识库]HDU Eight （BFS+康拓展开）

HDU1043 Eight

题目

给出数字八数码游戏的一种棋局状态，求完成游戏的步骤，输出
任意一种即可

思路

• 每种对弈状态可以抽象成一个1~ 9的数字排列，所以所有的可能就是1~9的全排列，总共是$10^6$级，因此可以穷举。
• 考虑搜索，从初始态穷举所有状态。首先，如何搜索，如果使用BFS，显然会造成重复，并且无法通过简单的打标记方法解决。
  但是，我们可以通过对他们的全排列进行编号，这样就可以采用标记解决。
• 那么，解决如何快速获取一对弈状态的全排列编号的问题。
  我们可以使用康拓展开,排列的编号是倒数第$i$个元素的逆序对数量和$(n?i?1)$的阶乘。
  代码实现如下：

int KT(int *s)
{
   int n = 9;//长度
   int res=0;
   for(int i=0;i<n;i++)
   {
      int ai = 0;
      for(int j=i+1;j<n;j++)//求逆序
         ai += s[i]>s[j];
      res += ai * fact(n-1-i);
   }
   return res;
}

• 现在我们可以顺利的跑完所有对弈状态，考虑其中需要记录的数据，显然要输出路径，我们在搜索中，需要储存移动方式$way$，同时，可以储存它的父亲节点$fa$，这样我们就可以不断向上回溯，直到回到最初状态。

AC代码

#include <bits/stdc++.h>
#define yes puts("yes");
#define inf 0x3f3f3f3f
#define linf 0x3f3f3f3f3f3f3f3f
#define ll long long
#define ull unsigned long long
#define debug(x) cout<<"> "<< x<<endl;
#define endl '\n'
//#define int long long
using namespace std;
typedef pair<int,int> PII;
const int N =370000, mod = 1e9 + 7;
int d[4][2] = {{1,0},{-1,0},{0,1},{0,-1}};
struct Node
{
   int num;
   int id9;
   int a[10];
   Node()
   {
      for(int i=0;i<10;i++)
         a[i] = i+1;
      id9 = 8;
      num = 0;
   }
   void swap(int _a,int _b)
   {
      int t = a[_a];
      a[_a] = a[_b];
      a[_b] = t;
   }
};
struct Ans
{
   char way;
   int fa;
}ans[N];// 初始状态父节点指向它自己

int fact(int n)
{
   if(n==0)return 1;
   return n*fact(n-1);
}

int KT(int *s)
{
   int n = 9;
   int res=0;
   for(int i=0;i<n;i++)
   {
      int ai = 0;
      for(int j=i+1;j<n;j++)
         ai += s[i]>s[j];
      res += ai * fact(n-1-i);
   }
   return res;
}

void bfs()
{
   Node s;
   queue<Node>q;
   q.push(s);
   while(q.size())
   {
      s = q.front();
      q.pop();
      for(int i=0;i<4;i++)
      {
         int nx = s.id9/3 +d[i][0];
         int ny = s.id9%3 + d[i][1];
         if(nx<0||ny<0||nx>=3||ny>=3) continue;
         Node v = s;
         int now_id9 = nx*3+ny;
         v.swap(s.id9,now_id9);
         v.id9 = now_id9;
         v.num = KT(v.a);
         if(ans[v.num].fa == -1)// 如果该状态还未遍历更新路径和父节点并入队
         {// u d l r 因为是倒着找，存的路径也倒过来
            if(i==0) ans[v.num].way = 'u';
            else if(i==1) ans[v.num].way = 'd';
            else if(i==2) ans[v.num].way = 'l';
            else ans[v.num].way = 'r'; 
            ans[v.num].fa = s.num;
            q.push(v);
         }
      }
   }
}

void solve()
{    
   char C[100];
   for(int i=0;i<N;i++) ans[i].fa = -1;// 初始化
   bfs();// 搜索，预处理所有可能
   while(gets(C))
   {
      int arr[10];
      for(int i=0,j=0;C[i]!='\0';++i)// 预处理格式规范化
         if(C[i]=='x') arr[j++] = 9;
         else if(isdigit(C[i])) arr[j++] = C[i]-'0';
      int pre_id = KT(arr);
      if(ans[pre_id].fa == -1)
      {
         cout<<"unsolvable\n";
         continue;
      }
      while(pre_id != 0)// 以父节点编号为索引，回溯
      {
         printf("%c",ans[pre_id].way);
         pre_id = ans[pre_id].fa;
      }
      puts("");
   }   
}
signed main()
{
    ios::sync_with_stdio();cin.tie();cout.tie();

    solve();

    return 0;
}