HDU 1043 & POJ 1077 Eight（康托展开+BFS

HDU 1043 & POJ 1077 Eight（康托展开+BFS | IDA*）

阅读量：5278 次

发布时间：2019-06-14

本文共 9089 字，大约阅读时间需要 30 分钟。

Eight

Time Limit: 1000MS		Memory Limit: 65536K
Total Submissions: 30176		Accepted: 13119		Special Judge

Description

The 15-puzzle has been around for over 100 years; even if you don't know it by that name, you've seen it. It is constructed with 15 sliding tiles, each with a number from 1 to 15 on it, and all packed into a 4 by 4 frame with one tile missing. Let's call the missing tile 'x'; the object of the puzzle is to arrange the tiles so that they are ordered as:

1  2  3  4  5  6  7  8  9 10 11 12 13 14 15  x

where the only legal operation is to exchange 'x' with one of the tiles with which it shares an edge. As an example, the following sequence of moves solves a slightly scrambled puzzle:

1  2  3  4    1  2  3  4    1  2  3  4    1  2  3  4  5  6  7  8    5  6  7  8    5  6  7  8    5  6  7  8  9  x 10 12    9 10  x 12    9 10 11 12    9 10 11 12 13 14 11 15   13 14 11 15   13 14  x 15   13 14 15  x            r->           d->           r->

The letters in the previous row indicate which neighbor of the 'x' tile is swapped with the 'x' tile at each step; legal values are 'r','l','u' and 'd', for right, left, up, and down, respectively.

Not all puzzles can be solved; in 1870, a man named Sam Loyd was famous for distributing an unsolvable version of the puzzle, and

frustrating many people. In fact, all you have to do to make a regular puzzle into an unsolvable one is to swap two tiles (not counting the missing 'x' tile, of course).

In this problem, you will write a program for solving the less well-known 8-puzzle, composed of tiles on a three by three

arrangement.

Input

You will receive a description of a configuration of the 8 puzzle. The description is just a list of the tiles in their initial positions, with the rows listed from top to bottom, and the tiles listed from left to right within a row, where the tiles are represented by numbers 1 to 8, plus 'x'. For example, this puzzle

1  2  3  x  4  6  7  5  8

is described by this list:

1 2 3 x 4 6 7 5 8

Output

You will print to standard output either the word ``unsolvable'', if the puzzle has no solution, or a string consisting entirely of the letters 'r', 'l', 'u' and 'd' that describes a series of moves that produce a solution. The string should include no spaces and start at the beginning of the line.

Sample Input

2  3  4  1  5  x  7  6  8

Sample Output

ullddrurdllurdruldr

Source

题目链接：

主要就是用康托展开来映射判重的问题，info::val就是康托展开hash值，info::step就是积累的状态。另外感觉这题剧毒，自己本来用int vis[]和char his[]想最后回溯记录答案从而代替速度比较慢的string，结果居然超时……TLE一晚上，要不是看了大牛的博客估计要一直T在这个坑点上。还有不知道为什么string的加号重载在C++编译器里会CE，换G++才过。相比单组输入的POJ，多组输入的HDU就友好多了，打个表就可以水过了，双广、A*神马的写起来麻烦就先不写了……

什么是康托展开？——

POJ代码：

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              
               #include
               
                #include
                
                 #include
                 
                  #include
                  using namespace std;#define INF 0x3f3f3f3f#define CLR(x,y) memset(x,y,sizeof(x))#define LC(x) (x<<1)#define RC(x) ((x<<1)+1)#define MID(x,y) ((x+y)>>1)typedef pair
                   
                     pii;typedef long long LL;const double PI = acos(-1.0);const int N = 362880 + 20;int fact[10] = {1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880};int direct[4][2] = { { -1, 0}, {1, 0}, {0, -1}, {0, 1}};char MOVE[5] = "udlr";struct info{ int s[9]; int indx; string step; int val;};info S, E;int T;int vis[N];string ans;int calcantor(int s[]){ int r = 0; for (int i = 0; i < 9; ++i) { int k = 0; for (int j = i + 1; j < 9; ++j) { if (s[j] < s[i]) ++k; } r = r + k * fact[8 - i]; } return r;}bool check(const int &x, const int &y){ return (x >= 0 && x < 3 && y >= 0 && y < 3);}bool bfs(){ CLR(vis, 0); queue
                    
                     Q; Q.push(S); vis[S.val] = 1; info now, v; while (!Q.empty()) { now = Q.front(); Q.pop(); if (now.val == T) { ans = now.step; return true; } for (int i = 0; i < 4; ++i) { int x = now.indx / 3; int y = now.indx % 3; x += direct[i][0]; y += direct[i][1]; if (check(x, y)) { v = now; v.indx = x * 3 + y; v.s[now.indx] = v.s[v.indx]; v.s[v.indx] = 0; v.val = calcantor(v.s); if (!vis[v.val]) { vis[v.val] = 1; v.step = now.step + MOVE[i]; if (v.val == T) { ans = v.step; return true; } Q.push(v); } } } } return false;}int main(void){ char temp; int i; T = 46233; while (cin >> temp) { if (temp == 'x') { S.s[0] = 0; S.indx = 0; } else S.s[0] = temp - '0'; for (i = 1; i < 9; ++i) { cin >> temp; if (temp == 'x') { S.s[i] = 0; S.indx = i; } else S.s[i] = temp - '0'; } S.val = calcantor(S.s); puts(!bfs() ? "unsolvable" : ans.c_str()); } return 0;}

HDU代码：

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              
               #include
               
                #include
                
                 #include
                 
                  #include
                  using namespace std;#define INF 0x3f3f3f3f#define CLR(x,y) memset(x,y,sizeof(x))#define LC(x) (x<<1)#define RC(x) ((x<<1)+1)#define MID(x,y) ((x+y)>>1)typedef pair
                   
                     pii;typedef long long LL;const double PI = acos(-1.0);const int N = 362880 + 10;int fact[10] = {1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880};struct info{ int s[9]; int indx; string path; int val; void cal() { val = 0; for (int i = 0; i < 9; ++i) { int k = 0; for (int j = i + 1; j < 9; ++j) { if (s[j] < s[i]) ++k; } val = val + k * fact[8 - i]; } }};info init = { {1, 2, 3, 4, 5, 6, 7, 8, 9}, 8, "", 0}, S;int direct[4][2] = { { -1, 0}, {1, 0}, {0, -1}, {0, 1}}; //ÏÂÉÏÓÒ×óchar MOV[5] = "durl";string ans[N];int vis[N];void bfs(){ CLR(vis, 0); queue
                    
                     Q; info now, v; Q.push(init); vis[init.val] = 1; ans[init.val] = init.path; while (!Q.empty()) { now = Q.front(); Q.pop(); for (int i = 0; i < 4; ++i) //ÏÂÉÏÓÒ×ó { int x = now.indx / 3; int y = now.indx % 3; x += direct[i][0]; y += direct[i][1]; if (x >= 0 && x < 3 && y >= 0 && y < 3) { v = now; v.indx = x * 3 + y; v.path = MOV[i] + now.path; swap(v.s[v.indx], v.s[now.indx]); v.cal(); if (!vis[v.val]) { vis[v.val] = 1; ans[v.val] = v.path; Q.push(v); } } } }}int main(void){ char temp[5], i; bfs(); while (~scanf("%s", temp)) { S.path = ""; if (temp[0] == 'x') { S.s[0] = 9; S.indx = 0; } else S.s[0] = temp[0] - '0'; for (i = 1; i < 9; ++i) { scanf("%s", temp); if (temp[0] == 'x') { S.s[i] = 9; S.indx = i; } else S.s[i] = temp[0] - '0'; } S.cal(); puts(!vis[S.val] ? "unsolvable" : ans[S.val].c_str()); } return 0;}

最近学了下IDA*，发现速度贼快，比哈希的不知道高到哪里去了，自己整理了一下一般写法，感觉还是比较模版的，可以参考上一篇IDA*的伪代码，IDA*快到如果用BFS要打表的HDU上的数据可以直接在线搜索过了，确实比较快，这里需要加一个防止走回路的剪枝（有效减少无用搜索），否则可能会超时，当然一开始要判断一下是否输入序列是无解的，可以暂时把x忽略掉，然后算7个数的逆序数，逆序数偶数才有解，奇数直接输出unsolvable，具体原理可以百度一下

代码：

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               
                #include 
                
                 #include 
                 
                  #include 
                  
                   #include 
                   using namespace std;#define INF 0x3f3f3f3f#define LC(x) (x<<1)#define RC(x) ((x<<1)+1)#define MID(x,y) ((x+y)>>1)#define CLR(arr,val) memset(arr,val,sizeof(arr))#define FAST_IO ios::sync_with_stdio(false);cin.tie(0);typedef pair
                    
                      pii;typedef long long LL;const double PI = acos(-1.0);const int N = 9;int arr[N], T[N] = {1, 2, 3, 4, 5, 6, 7, 8, 0};int Maxdep, top, stdpos[N] = {8, 0, 1, 2, 3, 4, 5, 6, 7};char Ops[1010];int dis(int cur, int ori){ int x = cur / 3, y = cur % 3; return abs(x - ori / 3) + abs(y - ori % 3);}int Need(int A[]){ int ret = 0; for (int i = 0; i < N; ++i) if (A[i] != T[i]) ret += dis(i, stdpos[A[i]]); return ret;}inline bool check(int x, int y){ return x >= 0 && x < 3 && y >= 0 && y < 3;}int dfs(int dep, int Arr[], char pre){ int need = Need(Arr); if (need == 0) return 1; else if (need + dep > Maxdep) return 0; else { int x, y, idx, i; int Temp[N]; for (int i = 0; i < N; ++i) { if (Arr[i] == 0) { idx = i; break; } } x = idx / 3, y = idx % 3; if (pre != 'u' && check(x + 1, y)) { for (i = 0; i < N; ++i) Temp[i] = Arr[i]; swap(Temp[(x + 1) * 3 + y], Temp[idx]); Ops[top++] = 'd'; if (dfs(dep + 1, Temp, 'd')) return 1; else --top; } if (pre != 'l' && check(x, y + 1)) { for (i = 0; i < N; ++i) Temp[i] = Arr[i]; swap(Temp[x * 3 + y + 1], Temp[idx]); Ops[top++] = 'r'; if (dfs(dep + 1, Temp, 'r')) return 1; else --top; } if (pre != 'd' && check(x - 1, y)) { for (i = 0; i < N; ++i) Temp[i] = Arr[i]; swap(Temp[(x - 1) * 3 + y], Temp[idx]); Ops[top++] = 'u'; if (dfs(dep + 1, Temp, 'u')) return 1; else --top; } if (pre != 'r' && check(x, y - 1)) { for (i = 0; i < N; ++i) Temp[i] = Arr[i]; swap(Temp[x * 3 + y - 1], Temp[idx]); Ops[top++] = 'l'; if (dfs(dep + 1, Temp, 'l')) return 1; else --top; } } return 0;}int main(void){ char n[3]; int i, j, x; while (~scanf("%s", n)) { if (n[0] == 'x') x = 0; else x = n[0] - '0'; arr[0] = x; for (i = 1; i < 9; ++i) { scanf("%s", n); if (n[0] == 'x') x = 0; else x = n[0] - '0'; arr[i] = x; } int inv = 0; for (i = 0; i < N; ++i) { if (arr[i] == 0) continue; for (j = i + 1; j < N; ++j) { if (arr[j] == 0) continue; if (arr[i] > arr[j]) ++inv; } } if (inv & 1) puts("unsolvable"); else { top = 0; Maxdep = 1; while (!dfs(0, arr, -1)) ++Maxdep; Ops[top] = '\0'; puts(Ops); } } return 0;}

转载于:https://www.cnblogs.com/Blackops/p/5816604.html

你可能感兴趣的文章