F - Eight Puzzle
Time Limit: 3000/1000MS (Java/Others) Memory Limit: 65535/65535KB (Java/Others)
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 a4 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. To simplify this problem, you should print the minimum steps only.
Input
There are multiple test cases.
For each test case, 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.Otherwise, output an integer which equals the minimum steps.
Sample input and output
| Sample Input | Sample Output |
|---|---|
1 2 x 4 5 3 7 8 6 |
2 |
Hint
Any violent algorithm may gain TLE. So a smart method is expected.
The data used in this problem is unofficial data prepared by hzhua. So any mistake here does not imply mistake in the offcial judge data.
解题报告:
HINT部分已经知道本题数据很强，因此暂时不考虑普通bfs,那么我们可以考虑双广和A*两种算法..
关于两种方法的结果:
1.A*超时
2.双广AC
可能的原因：首先如果没有解，都退化成普通bfs，这点并没有区别，那么只能说明在有解的时候双广比A*高效很多
当然效率还可以进一步提升，那就是奇偶性剪枝，想了解的话可以百度
双广代码(有奇偶性剪枝)
#include <iostream> #include <cstring> #include <cstdio> using namespace std; const int maxhashsize = 362880 + 500; const int maxstatussize = 1e6 + 500; int vis1[maxhashsize],vis2[maxhashsize]; int fac[10]; int dir[4][2] = {-1,0,1,0,0,-1,0,1}; typedef struct status { char s[9] , step; int val; }; status q1[maxstatussize],q2[maxstatussize]; int gethashvalue(const status &x) { int res = 0; for(int i = 0 ; i < 9 ; ++ i) { int cot = 0; for(int j = i+1 ; j < 9 ; ++ j) if (x.s[i] > x.s[j]) cot++; res += fac[8-i]*cot; } return res; } status st,ed; int bfs() { int front1 = 0 , rear1 = 0; int front2 = 0 , rear2 = 0; q1[rear1++] = st; q2[rear2++] = ed; if (st.val == ed.val ) return 0; while(front1 < rear1 || front2 < rear2) { // { status ns = q1[front1++]; int x,y,step = ns.step,oripos; for(int i = 0 ; i < 9 ; ++ i) if (!ns.s[i]) { x = i / 3 ; y = i % 3; oripos = i; break; } for(int i = 0 ; i < 4 ; ++ i) { int newx = x + dir[i][0]; int newy = y + dir[i][1]; if (newx >= 3 || newx < 0 || newy >= 3 || newy < 0) continue; int newpos = newx*3+newy; status ss; memcpy(&ss,&ns,sizeof(struct status)); swap(ss.s[newpos],ss.s[oripos]); int newhash = gethashvalue(ss); if (vis1[newhash] != -1) continue; ss.step ++ ; if (vis2[newhash] != -1) return ss.step + vis2[newhash]; vis1[newhash] = ss.step; ss.val = newhash; q1[rear1++] = ss; } } //************************** { status ns = q2[front2++]; int x,y,step = ns.step,oripos; for(int i = 0 ; i < 9 ; ++ i) if (!ns.s[i]) { x = i / 3 ; y = i % 3; oripos = i; break; } for(int i = 0 ; i < 4 ; ++ i) { int newx = x + dir[i][0]; int newy = y + dir[i][1]; if (newx >= 3 || newx < 0 || newy >= 3 || newy < 0) continue; int newpos = newx*3+newy; status ss; memcpy(&ss,&ns,sizeof(struct status)); swap(ss.s[newpos],ss.s[oripos]); int newhash = gethashvalue(ss); if (vis2[newhash] != -1) continue; ss.step ++ ; if (vis1[newhash] != -1) return ss.step + vis1[newhash]; vis2[newhash] = ss.step; ss.val = newhash; q2[rear2++] = ss; } } } return -1; } bool input() { char ch = getchar(); if (ch == EOF) return false; memset(vis1,-1,sizeof(vis1)); memset(vis2,-1,sizeof(vis2)); if (ch == 'x') st.s[0] = 0; else st.s[0] = ch-'0'; getchar(); for(int i = 1 ; i <= 8 ; ++ i) { ch = getchar();getchar(); if (ch == 'x') st.s[i] = 0; else st.s[i] = ch-'0'; } st.step = 0; vis1[gethashvalue(st)] = 0; // Init for vis st.val = gethashvalue(st); vis2[gethashvalue(ed)] = 0; ed.val = gethashvalue(ed); return true; } int main(int argc,char *argv[]) { fac[0] = 1; for(int i = 1 ; i <= 8 ; ++ i) fac[i] = i*fac[i-1]; for(int i = 0 ; i < 9 ; ++ i) ed.s[i] = i + 1; ed.s[8] = 0; ed.step = 0; while(input()) { int sum = 0; //奇偶性判断 for(int i = 0 ; i < 9 ; ++ i) { if (st.s[i] == 0) continue; for(int j = 0 ; j < i ; ++ j) if (st.s[j] > st.s[i]) sum++; } if ( sum % 2 & 1) { cout << "unsolvable" << endl; continue; } int ans = bfs(); if (ans == -1) cout << "unsolvable" << endl; else cout << ans << endl; } return 0; }