您现在的位置是:首页 > 正文

LA 5506 Eight

2024-02-29 15:24:58阅读 1

         同样是South Central USA 1998的题,POJ和HDU上的数据比较水,用BFS不加任何优化都可以AC,时间一般是三位数左右。而用A*或IDA*则可以把时间控制在10ms左右,甚至0ms!

         然而UVa Live上的这道题是多数据的,用IDA*不加优化都会超时。除此之外题目输入输出很严格,case和case之间必须有空行,在最后一组case之后不能有空行,否则会Wrong Answer..


        优化很简单,就是在搜索之前就判断一下是否有解。如果除去x之外的数字序列的逆序数是偶数,则有解;否则无解。因为在上下左右移动的过程中,数列的逆序数是不会产生变化的(在纸上画画就知道)。而目标状态的逆序数是偶数的,所以如果当前的数列逆序数是奇数则必定不能转移到目标状态。

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int tar[10][2]={{-1,-1},{0,0},{0,1},{0,2},{1,0},{1,1},{1,2},{2,0},{2,1},{2,2}};
int abs(int x)
{
    return x>0?x:-x;
}
int sum;
int msb[10],msa[10];
int MergeSort(int s,int e)
{
    int mid,cnt,t1,t2,i;
    if (s >= e-1)
        return 0;
    mid=(s+e)>>1;
    cnt=MergeSort(s,mid)+MergeSort(mid,e);
    t1=s;
    t2=mid;
    i=s;
    while (t1 < mid && t2 < e)
    {
        if (msa[t1] > msa[t2])
        {
            msb[i]=msa[t1];
            t1++;
            i++;
            cnt+=t2-mid;
        }
        else
        {
            msb[i]=msa[t2];
            t2++;
            i++;
        }
    }
    while (t1 < mid)
    {
        msb[i]=msa[t1];
        i++;
        t1++;
        cnt+=t2-mid;
    }
    while (t2 < e)
    {
        msb[i]=msa[t2];
        i++;
        t2++;
    }
    for (i=s; i<e; i++)
        msa[i]=msb[i];
    return cnt;
}
void swap(int &a,int &b)
{
    int t;
    t=a;
    a=b;
    b=t;
}
class Board
{
public:
    int a[3][3];
    int x,y;
    int h;
    void readIn()
    {
        int i,j;
        char str[2];
        for (i=0; i<3; i++)
        {
            for (j=0; j<3; j++)
            {
                scanf("%s",str);
                if (str[0] == 'x')
                {
                    a[i][j]=0;
                    x=i;
                    y=j;
                }
                else
                    a[i][j]=str[0]-'0';
            }
        }
    }
    void printOut()
    {
        int i,j;
        for (i=0; i<3; i++)
        {
            for (j=0; j<3; j++)
            {
                printf("%d ",a[i][j]);
            }
            printf("\n");
        }
        printf("h=%d\n",getH());
    }

    bool checkLegal()
    {
        int b[10],i,j,k;
        k=0;
        for (i=0; i<3; i++)
        {
            for (j=0; j<3; j++)
            {
                msa[k]=a[i][j];
                if (msa[k] != 0)
                    k++;
            }
        }
        sum=MergeSort(0,8);
        if (sum%2 == 1)
            return false;
        return true;
    }
    int getH()
    {
        int cnt,i,j;
        cnt=0;
        for (i=0; i<3; i++)
        {
            for (j=0; j<3; j++)
            {
                if (a[i][j] != 0)
                    cnt+=abs(i-tar[a[i][j]][0])+abs(j-tar[a[i][j]][1]);
            }
        }
        h=cnt;
        return cnt;
    }
    bool moveUp()
    {
        if (x == 0)
            return false;
        swap(a[x-1][y],a[x][y]);
        x--;
        return true;
    }
    bool moveDown()
    {
        if (x == 2)
            return false;
        swap(a[x+1][y],a[x][y]);
        x++;
        return true;
    }
    bool moveLeft()
    {
        if (y == 0)
            return false;
        swap(a[x][y-1],a[x][y]);
        y--;
        return true;
    }
    bool moveRight()
    {
        if (y == 2)
            return false;
        swap(a[x][y+1],a[x][y]);
        y++;
        return true;
    }
};
int lim;
char ans[120];
bool IDDFS(int dep,Board b,char pr)
{
    /*printf("%d %d\n",dep,lim);
    b.printOut();
    getchar();*/
    Board tb;
    b.getH();
    if (b.h == 0)
        return true;
    if (dep > lim)
        return false;
    if (b.h+dep > lim)
        return false;
    tb=b;
    if (pr != 'd' && (tb.moveUp() == true))
    {
        ans[dep]='u';
        if (IDDFS(dep+1,tb,'u') == true)
            return true;
    }
    tb=b;
    if (pr != 'u' && (tb.moveDown() == true))
    {
        ans[dep]='d';
        if (IDDFS(dep+1,tb,'d') == true)
            return true;
    }
    tb=b;
    if (pr != 'r' && (tb.moveLeft() == true))
    {
        ans[dep]='l';
        if (IDDFS(dep+1,tb,'l') == true)
            return true;
    }
    tb=b;
    if (pr != 'l' && (tb.moveRight() == true))
    {
        ans[dep]='r';
        if (IDDFS(dep+1,tb,'r') == true)
            return true;
    }
    return false;
}
int main()
{
    int prob;
    Board b;
    scanf("%d",&prob);
    while (prob--)
    {
        b.readIn();
        b.getH();
        if (b.h == 0)
        {
            printf("\n");
            if (prob > 0)
                printf("\n");
            continue;
        }
        if (b.checkLegal() == false)
        {
            printf("unsolvable\n");
            if (prob > 0)
                printf("\n");
            continue;
        }
        for (lim=1; lim<100; lim++)
        {
            if (IDDFS(0,b,'w') == true)
                break;
        }
        if (lim == 100)
        {
            printf("unsolvable\n");
            if (prob > 0)
                printf("\n");
        }
        else
        {
            ans[lim]='\0';
            printf("%s\n",ans);
            if (prob > 0)
                printf("\n");
        }
    }
}


网站文章

  • STM32 FOC电机PID学习笔记

    STM32 FOC电机PID学习笔记

    简介 在系统上存在外部干扰的情况下反馈是最好的选择否则使用前馈网络。 为扭矩、通量和速度实施的调节器实际上是比例(P Proportional )、积分(I Integral)、微分 (D Deriv...

    2024-02-29 15:24:31
  • 计算机毕业设计之php的网上汽车销售系统

    计算机毕业设计之php的网上汽车销售系统

    基于php的汽车销售网站将不同的车展示在自己的网站上,用户通过该网站,不仅可以了解各种车款的详情,还能在线预订任何一款爱车,然后到相关的汽车销售实体店现场看车、验车、试车、讨价还价、如果最后满意并确定...

    2024-02-29 15:24:25
  • Android - Intent与IntentFilter

    Android - Intent与IntentFilter

    Intent类的注释: 一个intent是要被执行的操作的一种抽象的描述,结合Context.Java类中定义的几个方法 —— [java] view plain copy &quot;background-color: rgb(255, 255, 255);&quot;&gt;&quot;font-family:Microsoft YaHei;font

    2024-02-29 15:24:17
  • 高中作文计算机与算盘,电脑与算盘作文600字

    在一个宽敞明亮的书房里,一排排书整齐地排列在书柜里,一台电脑正霸气地坐在主人的办公桌上。随着“嗒嗒嗒”键盘敲击的声音,一组组数据被输入进去快速地运行着,很快完成了计算任务。台灯、笔盒、书……大家都用崇...

    2024-02-29 15:24:11
  • ES6整理笔记

    一、 数组的解构赋值 1.1 ES6 允许按照一定模式,从数组和对象中提取值,对变量进行赋值,这被称为解构 。 以前为变量赋值,只能直接指定值。例如 let a = 1; let b = 2; let...

    2024-02-29 15:23:41
  • Spring Cloud学习 | 第一章 | 背景介绍

    (1):很久没有更新过自己的博客了,因为这段时间也在学习Spring Cloud,但是现目前国内资料还不是很多,而且搜出来的资料都千篇一律,学习起来非常恼火! 所以很多东西都智能从官方文档上慢慢的去学习,如果敲好您也在学习,或许可以让您节省一些时间,少走一些弯路! (2):学习一个新的知识点之前,我们还是需要花一部分的时间去了解该知识点的背景,组成,作用。就像我们写小说一样总有三要素,

    2024-02-29 15:23:35
  • 【算法笔记】Day04 |  2.5数组

    【算法笔记】Day04 | 2.5数组

    本节目录2.5.1 一维数组A.定义B.初始化C.递推2.5.2 冒泡排序A.算法内理解B.算法实现b1.交换2个数b2.冒泡排序实现2.5.3 二维数组A.定义B.初始化C.运算D.大型数组声明位置...

    2024-02-29 15:23:30
  • JDK8的新特性--lamdba表达式

    JDK8的新特性--lamdba表达式

    Lambda引入了新的操作符->(箭头操作符),->将表达式分成两部分左侧(参数1,参数2--)表示参数列表右侧{}内部是方法体

    2024-02-29 15:23:01
  • 5、微信小程序-网络请求和本地存储

    5、微信小程序-网络请求和本地存储

    文章目录前言一、准备二、网络请求1.微信小程序请求网络的方法2.发送网络请求3.网络请求的封装4.网络返回请求数据的处理三、本地存储 前言 这节我们来看下在微信小程序中如何进行网络请求的。 一、准备 ...

    2024-02-29 15:22:55
  • 手把手教会你开发动态web项目(2)

    手把手教会你开发动态web项目(2)

    这一章主要讲项目的结构。1. 项目使用gradle进行管理,如果你熟悉可以跳过这段,这里简单介绍一下。Gradle是一个类似于maven的项目管理构建工具,配置文件为项目根目录底下的build.gradle,你可以在这里配置项目的第三方依赖包。dependencies { def springFrameworkVersion = "4.2.5.RELEASE"compile...

    2024-02-29 15:22:48