首页 > 代码库 > POJ 1077 Eight

POJ 1077 Eight

2024-07-11 14:13:43   222人阅读

Eight
Time Limit: 1000MS Memory Limit: 65536K
Total Submissions: 23815 Accepted: 10518 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

South Central USA 1998
 
解题:这题比杭电那题要容易一点，本代码可以过poj的，但是过不了hdu的1043，正在学习IDA*以及如何破解1043.本题代码是来自某牛人的博客！学习IDA*时看了很多关于八数码的代码，只有这份代码，思路清晰，代码量少，拿来学习研究IDA*那是极好的。
 
 1 #include<iostream> 2 #include<cstdio> 3 #include<cstdlib> 4 using namespace std; 5 #define SIZE 3 6 char board[SIZE][SIZE]; 7 int goal_state[9][2] = {{0,0}, {0,1}, {0,2},{1,0}, {1,1}, {1,2}, {2,0}, {2,1}, {2,2}}; 8 int h(char board[][SIZE]) { 9     int cost = 0;10     for(int i=0; i<SIZE; ++i)11         for(int j=0; j<SIZE; ++j) {12             if(board[i][j] != SIZE*SIZE) {13                 cost += abs(i - goal_state[board[i][j]-1][0]) +14                         abs(j - goal_state[board[i][j]-1][1]);15             }16         }17     return cost;18 }19 int step[4][2] = {{-1, 0}, {0, -1}, {0, 1}, {1, 0}};//u, l, r, d20 char op[4] = {‘u‘, ‘l‘, ‘r‘, ‘d‘};21 char solution[1000];22 int bound;23 bool ans;24 int DFS(int x, int y, int dv, char pre_move) {25     int hv = h(board);26     if(hv + dv > bound) return dv + hv;27     if(hv == 0) {ans = true;return dv;}28     int next_bound = 1e9;29     for(int i = 0; i < 4; ++i) {30         if(i + pre_move == 3) continue;31         int nx = x + step[i][0];32         int ny = y + step[i][1];33         if(0 <= nx && nx < SIZE && 0 <= ny && ny < SIZE) {34             solution[dv] = i;35             swap(board[x][y], board[nx][ny]);36             int new_bound = DFS(nx, ny, dv+1, i);37             if(ans) return new_bound;38             next_bound = min(next_bound, new_bound);39             swap(board[x][y], board[nx][ny]);40         }41     }42     return next_bound;43 }44 void IDA_star(int sx, int sy) {45     ans = false;46     bound = h(board);47     while(!ans && bound <= 100) bound = DFS(sx, sy, 0, -10);48 }49 int main() {50     int sx, sy;51     char c;52     for(int i=0; i<SIZE; ++i)53         for(int j=0; j<SIZE; ++j) {54             cin>>c;55             if(c == ‘x‘) {56                 board[i][j] = SIZE * SIZE;57                 sx = i;58                 sy = j;59             } else board[i][j] = c - ‘0‘;60         }61     IDA_star(sx, sy);62     if(ans) {63         for(int i = 0; i < bound; ++i)64             cout<<op[solution[i]];65     } else cout<<"unsolvable";66     return 0;67 }
View Code

 


联系
我们