HDU 1403 Eight&POJ 1077(康拖,A* ,BFS,双广)

Eight

Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 18153 Accepted Submission(s): 4908 Special Judge

Problem 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, 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

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

Sample Input 2 3 4 1 5 x 7 6 8

Sample Output ullddrurdllurdruldr

解决这道题目,有很多方法,比如双广,BFS打表,A*+简单估价函数,A*+曼哈顿距离,IDA*+曼哈顿距离。但是这些方法都是基于在康托展开的基础上,别的状态表示都会超时。关于康托展开给出一篇博客把 http://blog.csdn.net/Dacc123/article/details/50952079

还有这道题目在poj和hdu上的测试数据是不同的,hdu上的数据比较多吧,poj水一点。

双广,从起始和结尾同时bfs,用康托展开表示状态 hdu看数据的,有的时候是可以过的4960ms。双广还是效率比较低的,poj 188ms

#include <iostream>
#include <string.h>
#include <stdlib.h>
#include <algorithm>
#include <math.h>
#include <stdio.h>
#include <queue>
#include <map>
#include <string>

using namespace std;
struct Node
{
    int a[3][3];
    int x,y;
    int state,id;
    Node(){};
    Node(int a[3][3],int x,int y,int state,int id)
    {
        this->id=id;
        this->x=x;
        this->y=y;
        this->state=state;
        memcpy(this->a,a,sizeof(this->a));
    }
};
queue<Node>q;
string f[2][500000];
int dir[4][2]={{1,0},{-1,0},{0,1},{0,-1}};
int fac[10];
int s[2];
char m[2][5]={"udlr","durl"};
char str[105];
void facfun()
{

    fac[0]=1;
    for(int i=1;i<=9;i++)
        fac[i]=fac[i-1]*i;
}
int kangtuo(int a[3][3])
{
    int sum=0,num;
    for(int i=0;i<9;i++)
    {
        num=0;
        for(int j=i+1;j<9;j++)
        {
            if(a[i/3][i%3]>a[j/3][j%3])
                num++;
        }
        sum+=num*fac[8-i];
    }
    return sum;
}
bool isok(int a[3][3])
{
    int num=0;
    for(int i=0;i<9;i++)
    {
        for(int j=i+1;j<9;j++)
        {
            if(a[i/3][i%3]!=9&&a[j/3][j%3]!=9&&a[i/3][i%3]>a[j/3][j%3])
                num++;
        }
    }
    return !(num&1);
}
void bfs(Node st,Node ed)
 {
    memset(f,0,sizeof(f));
    q.push(st);q.push(ed);
    s[1]=st.state;s[0]=ed.state;
    f[1][s[1]]="";  f[0][s[0]] = "";  
    while(!q.empty())
    {
        Node term=q.front();
        q.pop();
        for(int i=0;i<4;i++)
        {
            int xx=term.x+dir[i][0];
            int yy=term.y+dir[i][1];
            if(xx<0||xx>=3||yy<0||yy>=3)
                continue;
            swap(term.a[xx][yy],term.a[term.x][term.y]);
            int state=kangtuo(term.a);
            if(!f[term.id][state][0])
            {
                if(term.id)
                   f[term.id][state]=f[term.id][term.state]+m[term.id][i];
                else
                     f[term.id][state]=m[term.id][i]+f[term.id][term.state];
                if(f[1-term.id][state][0])
                {
                    cout<<f[1][state]<<f[0][state]<<endl;
                    return;
                }
                else
                   q.push(Node(term.a,xx,yy,state,term.id));
            }

            swap(term.a[xx][yy],term.a[term.x][term.y]);
        }
    }
    //printf("unsolvable\n");
}
int main()
{
    while(gets(str))
    {
        while(!q.empty())
            q.pop();
        facfun();
        Node st;
        int len=strlen(str);
        int cot=0;
        for(int i=0;i<len;i++)
        {
            if(str[i]!=' ')
            {
                if(str[i]=='x')
                {
                    st.a[cot/3][cot%3]=9;
                    st.x=cot/3;st.y=cot%3;
                }
                else
                    st.a[cot/3][cot%3]=str[i]-'0';
                cot++;
            }
        }
        st.id=1;st.state=kangtuo(st.a);
        Node ed;
        cot=1;
        for(int i=0;i<3;i++)
            for(int j=0;j<3;j++)
                ed.a[i][j]=cot++;
        ed.x=2;ed.y=2;ed.id=0;ed.state=kangtuo(ed.a);
        if(!isok(st.a))
        {
            printf("unsolvable\n");
            continue;
        }
        bfs(st,ed);
    }
    return 0;
}

BFS打表:从结果往前面扫,把每一种状态到结果的步数记录下来。 hdu 109ms poj 989ms

#include <iostream>
#include <string.h>
#include <stdlib.h>
#include <algorithm>
#include <math.h>
#include <stdio.h>
#include <map>
#include <queue>

using namespace std;
int fac[]={1,1,2,6,24,120,720,5040,40320};
int dir[4][2]={{1,0},{-1,0},{0,1},{0,-1}};
struct Node
{
    int a[5][5];
    int posx;
    int posy;
    int sta;
};
queue<Node> q;
bool vis[400000];
int res[400000];
int pre[400000];
char s[100];
int a1[100];
int a2[10];
map<int,char>m;
int kt(Node s)
{
    int cot=0;
    for(int i=1;i<=3;i++)
        for(int j=1;j<=3;j++)
            a2[++cot]=s.a[i][j];
    int sum=0,num;
    for(int i=1;i<=9;i++)
    {
        num=0;
        for(int j=i+1;j<=9;j++)
        {
            if(a2[i]>a2[j])
                num++;
        }
        sum+=num*fac[9-i];
    }
    return sum;
}
void bfs(Node a)
{
    q.push(a);
    vis[0]=1;
    while(!q.empty())
    {
        Node term=q.front();
        q.pop();
        for(int i=0;i<4;i++)
        {
            int xx=term.posx+dir[i][0];
            int yy=term.posy+dir[i][1];
            if(xx<1||xx>3||yy<1||yy>3)
                continue;
            Node temp=term;
            swap(temp.a[temp.posx][temp.posy],temp.a[xx][yy]);
            temp.posx=xx;temp.posy=yy;
            int state=kt(temp);temp.sta=state;
            if(vis[state])
                continue;
            pre[state]=term.sta;
            res[state]=i;
            vis[state]=1;
            q.push(temp);
        }
    }
}
void fun(int term)
{
    if(term==0)
        return;
    cout<<m[res[term]];
    fun(pre[term]);
}
int main()
{
    m[0]='u';m[1]='d';m[2]='l';m[3]='r';
    int cnt=1;
    Node t;
    for(int i=1;i<=3;i++)
        for(int j=1;j<=3;j++)
            t.a[i][j]=cnt++;
    t.posx=3;t.posy=3;t.sta=0;
    memset(vis,0,sizeof(vis));
    vis[0]=1;
    bfs(t);
    while(gets(s))
    {
        int x,y;
        int len=strlen(s);
        int cot=0;
        Node t3;
        for(int i=0;i<len;i++)
        {
            if(s[i]!=' ')
            {
                cot++;
                if(cot%3==0) { x=cot/3; y=3;}
                else { x=cot/3+1; y=cot%3;}
                if(s[i]=='x')
                    t3.a[x][y]=9;
                else
                    t3.a[x][y]=s[i]-'0';
            }
        }

        int target=kt(t3);
        if(!vis[target])
            printf("unsolvable\n");
        else
        {
            fun(target);
            cout<<endl;
        }

    }
    return 0;
}

A*+简单估价函数+优先队列 ,这里要加一个判断来对应unsolved,当初始状态的逆序数(除去要移动的版块)和目标状态的同偶或同奇,就一定可以到达,否则一定不能。 简单估价函数:可以以当前状态下,多少个数字的位置是不正确的,表示价值。

hdu 2964ms poj 0ms

#include <iostream>
#include <string.h>
#include <stdlib.h>
#include <algorithm>
#include <math.h>
#include <queue>
#include <stdio.h>
#include <string>
#include <map>


using namespace std;
#define MAX 400000
struct Node
{
    int a[3][3];//图的状态
    int x,y;//空格的位置
    int state;//康托展开
    int g,h;//估价函数g,h
    string s;//记录路径
    bool operator<(const Node a)const
    {
        return h==a.h?g>a.g:h>a.h;
    }
};
priority_queue<Node> q;
int fac[10];
int vis[MAX+5];
int dir[4][2]={{1,0},{-1,0},{0,1},{0,-1}};
map<int,char> m;
char c[100];
void facfun()
{
    m[0]='d';m[1]='u';m[2]='r';m[3]='l';
    fac[0]=1;
    for(int i=1;i<=9;i++)
        fac[i]=fac[i-1]*i;
}
//康托展开
int kangtuo(int a[3][3])
{
    int sum=0,num;
    for(int i=0;i<9;i++)
    {
        num=0;
        for(int j=i+1;j<9;j++)
        {
            if(a[i/3][i%3]>a[j/3][j%3])
                num++;
        }
        sum+=num*fac[8-i];
    }
    return sum;
}
//简单估价函数
int get(int a[3][3])
{
    int num=0;
    for(int i=0;i<8;i++)
    {
        if(a[i/3][i%3]!=i+1)
            num++;
    }
    return num;
}
void bfs(Node st)
{
    q.push(st);
    vis[st.state]=1;
    int sh=st.h;int sg=st.g;
    while(!q.empty())
    {
        Node temp;
        Node term=q.top();
        q.pop();
        if(term.state==0)
        {
           cout<<term.s<<endl;
           return;
        }
        for(int i=0;i<4;i++)
        {
            temp=term;
            int xx=temp.x+dir[i][0];
            int yy=temp.y+dir[i][1];
            if(xx<0||xx>2||yy<0||yy>2)
                continue;
            swap(temp.a[temp.x][temp.y],temp.a[xx][yy]);
            temp.x=xx;temp.y=yy;temp.s=term.s+m[i];
            temp.g=term.g+1;temp.h=get(temp.a);
            temp.state=kangtuo(temp.a);
            if(vis[temp.state])
                continue;

            vis[temp.state]=1;
            q.push(temp);

        }
    }
    printf("unsolvable\n");
}
bool isok(int a[3][3])
{
    int num=0;
    for(int i=0;i<9;i++)
    {
        for(int j=i+1;j<9;j++)
        {
            if(a[i/3][i%3]!=9&&a[j/3][j%3]!=9&&a[i/3][i%3]>a[j/3][j%3])
               num++;
        }
    }
    if(!(num&1))
        return true;
    else
        return false;
}
int main()
{
    while(gets(c))
    {
        facfun();
        while(!q.empty())
        {
            q.pop();
        }
        memset(vis,0,sizeof(vis));
        int len=strlen(c);
        Node start;
        int cot=0;
        for(int i=0;i<len;i++)
        {
            if(c[i]!=' ')
            {
                if(c[i]=='x')
                {
                    start.a[cot/3][cot%3]=9;
                    start.x=cot/3;start.y=cot%3;
                }
                else
                    start.a[cot/3][cot%3]=c[i]-'0';
                cot++;
            }
        }
        start.g=0;start.h=get(start.a);start.state=kangtuo(start.a);
        start.s="";
        if(!isok(start.a))
        {
            printf("unsolvable\n");
            continue;
        }

        bfs(start);
    }
    return 0;
}

A*+曼哈顿距离+优先队列 股价函数变成了曼哈顿距离 hdu 1450ms poj 0ms

#include <iostream>
#include <string.h>
#include <stdlib.h>
#include <algorithm>
#include <math.h>
#include <queue>
#include <stdio.h>
#include <string>
#include <map>


using namespace std;
#define MAX 400000
struct Node
{
    int a[3][3];//图的状态
    int x,y;//空格的位置
    int state;//康托展开
    int g,h;//估价函数g,h
    string s;//记录路径
    bool operator<(const Node a)const
    {
        return h==a.h?g>a.g:h>a.h;
    }
};
priority_queue<Node> q;
int fac[10];
int vis[MAX+5];
int dir[4][2]={{1,0},{-1,0},{0,1},{0,-1}};
map<int,char> m;
char c[100];
void facfun()
{
    m[0]='d';m[1]='u';m[2]='r';m[3]='l';
    fac[0]=1;
    for(int i=1;i<=9;i++)
        fac[i]=fac[i-1]*i;
}
//康托展开
int kangtuo(int a[3][3])
{
    int sum=0,num;
    for(int i=0;i<9;i++)
    {
        num=0;
        for(int j=i+1;j<9;j++)
        {
            if(a[i/3][i%3]>a[j/3][j%3])
                num++;
        }
        sum+=num*fac[8-i];
    }
    return sum;
}
//简单估价函数
int get(int a[3][3])
{
    int num=0;
   for(int i=0;i<3;i++)
   {
       for(int j=0;j<3;j++)
       {
           int x=(a[i][j]-1)/3;
           int y=(a[i][j]-1)%3;
           num+=abs(x-i)+abs(y-j);
       }
   }
    return num;
}
void bfs(Node st)
{
    q.push(st);
    vis[st.state]=1;
    int sh=st.h;int sg=st.g;
    while(!q.empty())
    {
        Node temp;
        Node term=q.top();
        q.pop();
        if(term.state==0)
        {
           cout<<term.s<<endl;
           return;
        }
        for(int i=0;i<4;i++)
        {
            temp=term;
            int xx=temp.x+dir[i][0];
            int yy=temp.y+dir[i][1];
            if(xx<0||xx>2||yy<0||yy>2)
                continue;
            swap(temp.a[temp.x][temp.y],temp.a[xx][yy]);
            temp.x=xx;temp.y=yy;temp.s=term.s+m[i];
            temp.g=term.g+1;temp.h=get(temp.a);
            temp.state=kangtuo(temp.a);
            if(vis[temp.state])
                continue;

            vis[temp.state]=1;
            q.push(temp);

        }
    }
    printf("unsolvable\n");
}
bool isok(int a[3][3])
{
    int num=0;
    for(int i=0;i<9;i++)
    {
        for(int j=i+1;j<9;j++)
        {
            if(a[i/3][i%3]!=9&&a[j/3][j%3]!=9&&a[i/3][i%3]>a[j/3][j%3])
               num++;
        }
    }
    if(!(num&1))
        return true;
    else
        return false;
}
int main()
{
    while(gets(c))
    {
        facfun();
        while(!q.empty())
        {
            q.pop();
        }
        memset(vis,0,sizeof(vis));
        int len=strlen(c);
        Node start;
        int cot=0;
        for(int i=0;i<len;i++)
        {
            if(c[i]!=' ')
            {
                if(c[i]=='x')
                {
                    start.a[cot/3][cot%3]=9;
                    start.x=cot/3;start.y=cot%3;
                }
                else
                    start.a[cot/3][cot%3]=c[i]-'0';
                cot++;
            }
        }
        start.g=0;start.h=get(start.a);start.state=kangtuo(start.a);
        start.s="";
        if(!isok(start.a))
        {
            printf("unsolvable\n");
            continue;
        }

        bfs(start);
    }
    return 0;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏小樱的经验随笔

HDU 2034 人见人爱A-B

人见人爱A-B Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (J...

31910
来自专栏ACM算法日常

String Problem(KMP+最小表示法)- HDU 3374

Give you a string with length N, you can generate N strings by left shifts. For ...

792
来自专栏一个会写诗的程序员的博客

《Kotin 极简教程》第7章 面向对象编程(OOP)(2)《Kotlin极简教程》正式上架:

在上面的代码中,我们通过向注解类添加元注解(meta-annotation)的方法来指定其他属性:

1522
来自专栏算法修养

ZOJ 3537 Cake(凸包判定+区间DP)

Cake Time Limit: 1 Second Memory Limit: 32768 KB You want to hold a par...

3659
来自专栏小灰灰

java之通过反射生成并初始化对象

java之通过反射生成并初始化对象 在博文 《java之的读取文件大全》 中读取csv文件后,需要自己将csv文件的对象转为自己的DO对象,那么有没有办法我...

1K6
来自专栏友弟技术工作室

golang之Struct什么是结构体struct?

最近在复习golang,学习的东西,如果不使用,很快就会忘记。所以,准备复习完golang,做一个练手的小项目,加深对golang的学习。今天开始公司,进入封闭...

5766
来自专栏PPV课数据科学社区

【工具】SAS数据整理的16个技巧

1、修改属性   attrib 2、根据条件删除记录   if条件 then delete; 3、分拆数据集 data mastermissing; me...

3485
来自专栏算法修养

HOJ 2985 Wavio Sequence(最长递增子序列以及其O(n*logn)算法)

Wavio Sequence My Tags (Edit) Source : UVA Time limit : 1 sec Memor...

2706
来自专栏增长技术

位运算

1042
来自专栏数据结构与算法

2570 绝对素数

2570 绝对素数 时间限制: 1 s 空间限制: 128000 KB 题目等级 : 黄金 Gold 题目描述 Description 一个自然数...

3507

扫码关注云+社区

领取腾讯云代金券