Hdu 1043 eight - dblank

Hdu 1043 eight

<div class="panel_content">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.</div>
<div class="panel_bottom"></div>
 
<div class="panel_title" align="left">Input</div>
<div class="panel_content">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</div>
<div class="panel_bottom"></div>
 
<div class="panel_title" align="left">Output</div>
<div class="panel_content">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.</div>
<div class="panel_bottom"></div>
 
<div class="panel_title" align="left">Sample Input</div>
<div class="panel_content">
<div>2 3 4 1 5 x 7 6 8</div>
</div>
<div class="panel_bottom"> 题意:给你一个起始的八数码状态,让你找到还原的操作方法,输出容易的方案就可以的。</div>
<div class="panel_bottom">思路:所有的解的最终目的都是一个状态,我们可以从最终状态出发,到达所有可以到达的点,然后打一个表,记录前驱路径。状态可以用全排列的编号来表示该状态,因为是反过来的,所以操作是反的。</div>
<div class="panel_bottom">

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<map>
#include<cstring>
#include<map>
#include<set>
#include<queue>
#include<stack>
#include<cmath>
using namespace std;
const double eps = 1e-10;
const int inf = 0x3f3f3f3f, N = 5000 + 10, Mod = 1000000000;
typedef long long ll;
char s[100], num[100];
struct node
{
    int status, pre;
    char run;
    node() {};
    node(int Status, int Pre, char Run):status(Status), pre(Pre), run(Run) {}
} pre[400000];
char run[] = "rlud";
int fact[10], vis[400000];
int get_hash(int x)
{
    char ss[20];
    sprintf(ss, "%09d", x);
    int res = 0;
    int mark[10];
    memset(mark, 0, sizeof(mark));
    for(int i = 0; i<9; i++)
    {
        int cnt = 0;
        mark[ss[i]-'0'] = 1;
        for(int j = 0; j<ss[i]-'0'; j++)
        {
            if(!mark[j])
                cnt++;
        }
        res += cnt * fact[8 - i];
    }
    return res;
}
char C[] = "rlud";
int change(int status, char c)
{
    char ss[20];
    sprintf(ss, "%09d", status);
    int id;
    for(int i = 0; ss[i]; i++)
    {
        if(ss[i] == '0')
        {
            id = i;
            break;
        }
    }
    if(c == 'd')
    {
        if(id/3 == 0)
            return -1;
        else
            swap(ss[id], ss[id-3]);
    }
    if(c == 'u')
    {
        if(id/3 == 2)
            return -1;
        else swap(ss[id], ss[id+3]);
    }
    if(c == 'r')
    {
        if(id%3 == 0)
            return -1;
        else swap(ss[id], ss[id-1]);
    }
    if(c == 'l')
    {
        if(id%3 == 2)
            return -1;
        else swap(ss[id], ss[id+1]);
    }
    return atoi(ss);
}
void bfs()
{
    int x, y, z;
    memset(vis, 0, sizeof(vis));
    vis[get_hash(123456780)] = 1;
    pre[get_hash(123456780)].pre = -1;
    queue<int> q;
    q.push(123456780);
    int ok = 0 ;
    while(!q.empty())
    {
        x = q.front();
        q.pop();
        for(int i = 0; i<4; i++)
        {
            y = change(x, C[i]);
            z = get_hash(y);
            if(!vis[z] && y!=-1)
            {
                pre[z].pre = get_hash(x);
                pre[z].run = C[i];
                vis[z] = 1;
                q.push(y);
            }
        }
    }
    return ;
}
int main()
{

    fact[0] = 1;
    for(int i = 1; i<=9; i++)
        fact[i] = fact[i-1] * i;
    bfs();
    while(gets(s))
    {
        int k = 0;
        for(int i = 0; s[i]; i++)
        {
            if(s[i]!=' ')
            {
                if(s[i] != 'x')
                    num[k++] = s[i];
                else num[k++] = '0';
            }
        }
        num[k] = 0;
        int sta = atoi(num);
        if(!vis[get_hash(sta)])
        {
            printf("unsolvablen");
        }
        else
        {
            if(sta == 123456780)
            {
                printf("lrn");
                continue;
            }
            int root = get_hash(sta);
            queue<char> ans;
            while(pre[root].pre!=-1)
            {
                ans.push(pre[root].run);
                root = pre[root].pre;
            }
            while(!ans.empty())
            {
                printf("%c", ans.front());
                ans.pop();
            }
            printf("n");
        }
    }
    return 0;
}

 

</div>

相关文章

仅有 1 条评论
  1. WilliamLot

    Trying To Find The Best Diet Pill?

    Trying to find the best diet pill may seem like an impossible task, especially with the multitude of diet pills available for purchase. Many people purchase a diet pill only to find out that the pill makes them feel jittery, nervous, or often has no effect at all.

    Diet pills frequently contain the same or similar combination of ingredients and rarely contain anything new, innovative, or undiscovered to the supplement / weight loss industry. So, how can you find the best diet pill when most diet pills are made with similar ingredients?

    One of the most common problems associated with taking diet pills is that the person taking the diet pill is uneducated about the dosage, effects, and promises offered as they relate to each diet pill. The research at website finds that there are three factors that should be taken into consideration when deciding to take a diet pill.

    Dosage:
    It is important to take the pill exactly as recommended on the product label. Some people choose to increase the dosage thinking that the product will work faster or better. This is not the case, and many people become sick in response to the large dose. Reviewers at website often suggest that the recommended dosage be cut in half to give the body time to adjust to the stimulant in the diet pill. After the body has adjusted, it is fine to begin taking the regular dosage as recommended on the product label.

    Effects:
    The effects listed on the product label are there because these are the effects that the product has had on 'some' of the test group. Some of the diet pill testers may be fine taking the product, while others may have adverse effects. The diet pill companies print this information to educate the buyer as well as to protect themselves from lawsuits. The consumer needs to read the label and educate themselves before taking the product. Many people who are sensitive to caffeine are surprised when the diet pill makes them feel nervous or nauseous, but this information is likely printed on the product, so with a little research these affects can be avoided.

    Promises:
    If you read the fine print on product claims for diet pills and other weight loss supplements, you will see 'results not typical' printed very small somewhere where you are not expected to look. The diet pills advertised on television are responsible for some of the most outlandish claims. The results claimed in these advertisements are often unattainable within the given amount of time outlined in the ad. Don't expect to see results in two weeks like a lot of ads claim.

    Wouldn't it be great if you could read reviews for diet pills from actual users of each diet pill? Diet Pill Reviews website has taken the trouble out of searching for the best diet pill. You can read reviews of over 150 of the most popular diet pills available.

    Copyright 2006, Diet Pill Reviews viagra pas cher

    WilliamLot 回复
发表新评论