正文

HDU 1043 & POJ 1077 Eight（康托展开+BFS | IDA*）

IP云
IP云V管理员/0 阅读
12/01
小程序：扫一扫查出行
【扫一扫了解最新限行尾号】
复制小程序
Eight
Time Limit: 1000MS Memory Limit: 65536K
Total Submissions: 30176 Accepted: 13119 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 1077

主要就是用康托展开来映射判重的问题，info::val就是康托展开hash值，info::step就是积累的状态。另外感觉这题剧毒，自己本来用int vis[]和char his[]想最后回溯记录答案从而代替速度比较慢的string，结果居然超时……TLE一晚上，要不是看了大牛的博客估计要一直T在这个坑点上。还有不知道为什么string的加号重载在C++编译器里会CE，换G++才过。相比单组输入的POJ，多组输入的HDU就友好多了，打个表就可以水过了，双广、A*神马的写起来麻烦就先不写了……

什么是康托展开？——康托展开介绍文章

POJ代码： 

#include<iostream>

#include<algorithm>

#include<cstdlib>

#include<sstream>

#include<cstring>

#include<bitset>

#include<cstdio>

#include<string>

#include<deque>

#include<stack>

#include<cmath>

#include<queue>

#include<set>

#include<map>

using namespace std;

#define INF 0x3f3f3f3f

#define CLR(x,y) memset(x,y,sizeof(x))

#define LC(x) (x<<1)

#define RC(x) ((x<<1)+1)

#define MID(x,y) ((x+y)>>1)

typedef pair<int, int> pii;

typedef long long LL;

const double PI = acos(-1.0);

const int N = 362880 + 20;

int fact[10] = {1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880};

int direct[4][2] = {{ -1, 0}, {1, 0}, {0, -1}, {0, 1}};

char MOVE[5] = "udlr";

struct info

{

    int s[9];

    int indx;

    string step;

    int val;

};

info S, E;

int T;

int vis[N];

string ans;

int calcantor(int s[])

{

    int r = 0;

    for (int i = 0; i < 9; ++i)

    {

        int k = 0;

        for (int j = i + 1; j < 9; ++j)

        {

            if (s[j] < s[i])

                ++k;

        }

        r = r + k * fact[8 - i];

    }

    return r;

}

bool check(const int &x, const int &y)

{

    return (x >= 0 && x < 3 && y >= 0 && y < 3);

}

bool bfs()

{

    CLR(vis, 0);

    queue<info>Q;

    Q.push(S);

    vis[S.val] = 1;

    info now, v;

    while (!Q.empty())

    {

        now = Q.front();

        Q.pop();

        if (now.val == T)

        {

            ans = now.step;

            return true;

        }

        for (int i = 0; i < 4; ++i)

        {

            int x = now.indx / 3;

            int y = now.indx % 3;

            x += direct[i][0];

            y += direct[i][1];

            if (check(x, y))

            {

                v = now;

                v.indx = x * 3 + y;

                v.s[now.indx] = v.s[v.indx];

                v.s[v.indx] = 0;

                v.val = calcantor(v.s);

                if (!vis[v.val])

                {

                    vis[v.val] = 1;

                    v.step = now.step + MOVE[i];

                    if (v.val == T)

                    {

                        ans = v.step;

                        return true;

                    }

                    Q.push(v);

                }

            }

        }

    }

    return false;

}

int main(void)

{

    char temp;

    int i;

    T = 46233;

    while (cin >> temp)

    {

        if (temp == 'x')

        {

            S.s[0] = 0;

            S.indx = 0;

        }

        else

            S.s[0] = temp - '0';

        for (i = 1; i < 9; ++i)

        {

            cin >> temp;

            if (temp == 'x')

            {

                S.s[i] = 0;

                S.indx = i;

            }

            else

                S.s[i] = temp - '0';

        }

        S.val = calcantor(S.s);

        puts(!bfs() ? "unsolvable" : ans.c_str());

    }

    return 0;

}

HDU代码： 

#include<iostream>

#include<algorithm>

#include<cstdlib>

#include<sstream>

#include<cstring>

#include<bitset>

#include<cstdio>

#include<string>

#include<deque>

#include<stack>

#include<cmath>

#include<queue>

#include<set>

#include<map>

using namespace std;

#define INF 0x3f3f3f3f

#define CLR(x,y) memset(x,y,sizeof(x))

#define LC(x) (x<<1)

#define RC(x) ((x<<1)+1)

#define MID(x,y) ((x+y)>>1)

typedef pair<int, int> pii;

typedef long long LL;

const double PI = acos(-1.0);

const int N = 362880 + 10;

int fact[10] = {1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880};

struct info

{

    int s[9];

    int indx;

    string path;

    int val;

    void cal()

    {

        val = 0;

        for (int i = 0; i < 9; ++i)

        {

            int k = 0;

            for (int j = i + 1; j < 9; ++j)

            {

                if (s[j] < s[i])

                    ++k;

            }

            val = val + k * fact[8 - i];

        }

    }

};

info init = {{1, 2, 3, 4, 5, 6, 7, 8, 9}, 8, "", 0}, S;

int direct[4][2] = {{ -1, 0}, {1, 0}, {0, -1}, {0, 1}}; //ÏÂÉÏÓÒ×ó

char MOV[5] = "durl";

string ans[N];

int vis[N];

void bfs()

{

    CLR(vis, 0);

    queue<info>Q;

    info now, v;

    Q.push(init);

    vis[init.val] = 1;

    ans[init.val] = init.path;

    while (!Q.empty())

    {

        now = Q.front();

        Q.pop();

        for (int i = 0; i < 4; ++i) //ÏÂÉÏÓÒ×ó

        {

            int x = now.indx / 3;

            int y = now.indx % 3;

            x += direct[i][0];

            y += direct[i][1];

            if (x >= 0 && x < 3 && y >= 0 && y < 3)

            {

                v = now;

                v.indx = x * 3 + y;

                v.path = MOV[i] + now.path;

                swap(v.s[v.indx], v.s[now.indx]);

                v.cal();

                if (!vis[v.val])

                {

                    vis[v.val] = 1;

                    ans[v.val] = v.path;

                    Q.push(v);

                }

            }

        }

    }

}

int main(void)

{

    char temp[5], i;

    bfs();

    while (~scanf("%s", temp))

    {

        S.path = "";

        if (temp[0] == 'x')

        {

            S.s[0] = 9;

            S.indx = 0;

        }

        else

            S.s[0] = temp[0] - '0';

        for (i = 1; i < 9; ++i)

        {

            scanf("%s", temp);

            if (temp[0] == 'x')

            {

                S.s[i] = 9;

                S.indx = i;

            }

            else

                S.s[i] = temp[0] - '0';

        }

        S.cal();

        puts(!vis[S.val] ? "unsolvable" : ans[S.val].c_str());

    }

    return 0;

}

最近学了下IDA*，发现速度贼快，比哈希的不知道高到哪里去了，自己整理了一下一般写法，感觉还是比较模版的，可以参考上一篇IDA*的伪代码，IDA*快到如果用BFS要打表的HDU上的数据可以直接在线搜索过了，确实比较快，这里需要加一个防止走回路的剪枝（有效减少无用搜索），否则可能会超时，当然一开始要判断一下是否输入序列是无解的，可以暂时把x忽略掉，然后算7个数的逆序数，逆序数偶数才有解，奇数直接输出unsolvable，具体原理可以百度一下

代码： 

#include <stdio.h>

#include <iostream>

#include <algorithm>

#include <cstdlib>

#include <sstream>

#include <numeric>

#include <cstring>

#include <bitset>

#include <string>

#include <deque>

#include <stack>

#include <cmath>

#include <queue>

#include <set>

#include <map>

using namespace std;

#define INF 0x3f3f3f3f

#define LC(x) (x<<1)

#define RC(x) ((x<<1)+1)

#define MID(x,y) ((x+y)>>1)

#define CLR(arr,val) memset(arr,val,sizeof(arr))

#define FAST_IO ios::sync_with_stdio(false);cin.tie(0);

typedef pair<int, int> pii;

typedef long long LL;

const double PI = acos(-1.0);

const int N = 9;

int arr[N], T[N] = {1, 2, 3, 4, 5, 6, 7, 8, 0};

int Maxdep, top, stdpos[N] = {8, 0, 1, 2, 3, 4, 5, 6, 7};

char Ops[1010];

int dis(int cur, int ori)

{

    int x = cur / 3, y = cur % 3;

    return abs(x - ori / 3) + abs(y - ori % 3);

}

int Need(int A[])

{

    int ret = 0;

    for (int i = 0; i < N; ++i)

        if (A[i] != T[i])

            ret += dis(i, stdpos[A[i]]);

    return ret;

}

inline bool check(int x, int y)

{

    return x >= 0 && x < 3 && y >= 0 && y < 3;

}

int dfs(int dep, int Arr[], char pre)

{

    int need = Need(Arr);

    if (need == 0)

        return 1;

    else if (need + dep > Maxdep)

        return 0;

    else

    {

        int x, y, idx, i;

        int Temp[N];

        for (int i = 0; i < N; ++i)

        {

            if (Arr[i] == 0)

            {

                idx = i;

                break;

            }

        }

        x = idx / 3, y = idx % 3;

        if (pre != 'u' && check(x + 1, y))

        {

            for (i = 0; i < N; ++i)

                Temp[i] = Arr[i];

            swap(Temp[(x + 1) * 3 + y], Temp[idx]);

            Ops[top++] = 'd';

            if (dfs(dep + 1, Temp, 'd'))

                return 1;

            else

                --top;

        }

        if (pre != 'l' && check(x, y + 1))

        {

            for (i = 0; i < N; ++i)

                Temp[i] = Arr[i];

            swap(Temp[x * 3 + y + 1], Temp[idx]);

            Ops[top++] = 'r';

            if (dfs(dep + 1, Temp, 'r'))

                return 1;

            else

                --top;

        }

        if (pre != 'd' && check(x - 1, y))

        {

            for (i = 0; i < N; ++i)

                Temp[i] = Arr[i];

            swap(Temp[(x - 1) * 3 + y], Temp[idx]);

            Ops[top++] = 'u';

            if (dfs(dep + 1, Temp, 'u'))

                return 1;

            else

                --top;

        }

        if (pre != 'r' && check(x, y - 1))

        {

            for (i = 0; i < N; ++i)

                Temp[i] = Arr[i];

            swap(Temp[x * 3 + y - 1], Temp[idx]);

            Ops[top++] = 'l';

            if (dfs(dep + 1, Temp, 'l'))

                return 1;

            else

                --top;

        }

    }

    return 0;

}

int main(void)

{

    char n[3];

    int i, j, x;

    while (~scanf("%s", n))

    {

        if (n[0] == 'x')

            x = 0;

        else

            x = n[0] - '0';

        arr[0] = x;

        for (i = 1; i < 9; ++i)

        {

            scanf("%s", n);

            if (n[0] == 'x')

                x = 0;

            else

                x = n[0] - '0';

            arr[i] = x;

        }

        int inv = 0;

        for (i = 0; i < N; ++i)

        {

            if (arr[i] == 0)

                continue;

            for (j = i + 1; j < N; ++j)

            {

                if (arr[j] == 0)

                    continue;

                if (arr[i] > arr[j])

                    ++inv;

            }

        }

        if (inv & 1)

            puts("unsolvable");

        else

        {

            top = 0;

            Maxdep = 1;

            while (!dfs(0, arr, -1))

                ++Maxdep;

            Ops[top] = '\0';

            puts(Ops);

        }

    }

    return 0;

}

HDU 1043 & POJ 1077 Eight（康托展开+BFS | IDA*）的更多相关文章
  1. Eight （HDU - 1043|POJ - 1077）(A* | 双向bfs+康拓展开)

    The 15-puzzle has been around for over 100 years; even if you don't know it by that name, you've see ...

  2. HDU 1043 & POJ 1077 Eight（康托展开+BFS+预处理）

    Eight Time Limit: 1000MS   Memory Limit: 65536K Total Submissions: 30176   Accepted: 13119   Special ...

  3. HDU 1430 魔板（康托展开+BFS+预处理）

    魔板 Time Limit: 10000/5000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others) Total Submis ...

  4. Eight hdu 1043 poj 1077

    Description The 15-puzzle has been around for over 100 years; even if you don't know it by that name ...

  5. HDU 1043 Eight (A* + HASH + 康托展开)

    Eight Time Limit: 10000/5000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others) Total Sub ...

  6. HDU 3567 Eight II 打表,康托展开,bfs,g++提交可过c++不可过 难度:3

    http://acm.hdu.edu.cn/showproblem.php?pid=3567 相比Eight,似乎只是把目标状态由确定的改成不确定的,但是康托展开+曼哈顿为h值的A*和IDA*都不过, ...

  7. hdu 1043 Eight (八数码问题)【BFS】+【康拓展开】

    <题目链接> 题目大意:给出一个3×3的矩阵(包含1-8数字和一个字母x),经过一些移动格子上的数后得到连续的1-8,最后一格是x,要求最小移动步数. 解题分析:本题用BFS来寻找路径,为 ...

  8. [HDOJ1043]Eight（康托展开 BFS 打表）

    题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1043 八数码问题,因为固定了位置所以以目标位置开始搜索,把所有情况(相当于一个排列)都记录下来,用康托 ...

  9. hdu1043Eight (经典的八数码)（康托展开+BFS）

    建议先学会用康托展开:http://blog.csdn.net/u010372095/article/details/9904497 Problem Description The 15-puzzle ...

随机推荐
  1. SpringMVC+Hibernate框架快速搭建

    1.  新建Maven项目springmvc 2.   pom.xml <project xmlns="http://maven.apache.org/POM/4.0.0" ...

  2. Jquery点击数字切换图片

    <!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/ ...

  3. Oracle Analyze

    Analyze使用场景 之前很多次都说到,对表的索引等信息进行了增删改之后,需要对表进行analyze更新统计信息,才能使数据库做出最好的执行计划,没有注意到,即使是一张很小的空表,如果进行了字段的增 ...

  4. primeng 中 pickList组件的使用

    primeng 是为angular 开发的一个强大的组建库,有很多强大的功能,拿来即用.但要真正满足自己的业务需求,就是按自己的需求进行修改,比如默认的样式等等. 进入正题. pickList 组件的 ...

  5. java算法面试题：编写一个程序，将a.txt文件中的单词与b.txt文件中的单词交替合并到c.txt文件中，a.txt文件中的单词用回车符分隔，b.txt文件中用回车或空格进行分隔。

    package com.swift; import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.File ...

  6. 如何在vue项目中使用md5加密

    npm安装: npm install --save js-md5 1.在需要使用的项目文件中引入: import md5 from 'js-md5'; 使用: md5('hello world') / ...

  7. 【转】【win网络编程】socket中的recv阻塞和select的用法

    在编写ftp客户端程序时,在联通后使用recv函数进行接收欢迎信息时,需要申请内存进行接收数据保存,一次读取成功,但是由于一个随机的ftp服务端在说,欢迎信息的大小是不知道的,所以在尝试使用死循环,在 ...

  8. 短信验证码js

    var isSmsSend = false; function clickButtona(obj){ var obj = $(obj); var mobile=$("input[name=m ...

  9. 传智 杨中科老师 ASP.NET 笔记

  10. JZOJ 3509. 【NOIP2013模拟11.5B组】倒霉的小C

    3509. [NOIP2013模拟11.5B组]倒霉的小C(beats) (File IO): input:beats.in output:beats.out Time Limits: 1000 ms ...

相关阅读

目录[+]