【题解】HDU-1043 Eight

Eight (HDU - 1043)

题面

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.

输入

You will receive, several descriptions of configuration of the 8 puzzle. One 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

输出

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. Do not print a blank line between cases.

样例输入

2  3  4  1  5  x  7  6  8

样例输出

ullddrurdllurdruldr

提示

无

思路

考虑多次bfs会TLE，而目标状态是确定的，且由此bfs出的所有状态也是有限的(9!)，所以这题不是bfs直接搜出来的，而是bfs打表。 暂时没用康拓展开，不过最好去看看，同时感兴趣的圣雄甘地可以了解一下八数码八境界…

代码

using namespace std;
typedef long long ll;
const int inf = 0x3f3f3f3f;
const int N = 1e2+5;

int n = 9;

int dx[] = { 1, -1,  0,  0};
int dy[] = { 0,  0,  1, -1};
char dir[] = "udlr";

struct P {
    string s, p;
    int x;
};

map<int, string> mp;

void bfs() {
    P sp;
    sp.s = "123456789";
    sp.p = "";
    sp.x = n-1;

    queue<P> q;
    q.push(sp);
    mp[123456789] = "";

    while(!q.empty()) {
        P tp = q.front();
        q.pop();

        P np;
        for(int i=0; i<4; i++) {
            int x = tp.x/3+dx[i];
            int y = tp.x%3+dy[i];
            if(x<0 || x>=3 || y<0 || y>=3) {
                continue;
            }
            np = tp;
            np.x = x*3+y;
            swap(np.s[np.x], np.s[tp.x]);

            int d=0;
            for(int i=0; i<n; i++) {
                d = d*10+np.s[i]-'0';
            }

            if(mp.find(d)==mp.end()) {
                np.p += i+'0';
                q.push(np);
                mp[d] = np.p;
            };
        }
    }
}

int main(void) {
    bfs();

    char c;
    while(scanf(" %c", &c)==1) {
        int d;
        if(c=='x') {
            d = 9;
        } else {
            d = c-'0';
        }
        for(int i=1; i<n; i++) {
            scanf(" %c", &c);
            if(c=='x') {
                d = d*10+9;
            } else {
                d = d*10+c-'0';
            }
        }
        if(mp.find(d)==mp.end()) {
            printf("unsolvable\n");
        } else {
            string p = mp[d];
            for(int i=p.length()-1; i>=0; i--)
                printf("%c", dir[p[i]-'0']);
            printf("\n");
        }
    }

    return 0;
}