UVALive 6665 Dragonas Cruller[通俗易懂]

UVALive 6665 Dragonas Cruller

大家好,又见面了,我是全栈君。

题目链接:https://icpcarchive.ecs.baylor.edu/external/66/6665.pdf

题目大意:

有一个3 * 3 的格子:

UVALive 6665 Dragonas Cruller[通俗易懂]

UVALive 6665 Dragonas Cruller[通俗易懂]

每个格子上面的数字能够朝上下左右四个方向移动。假设移出范围。则到与其边界上字母相应的还有一边。

例如以下图所看到的:

UVALive 6665 Dragonas Cruller[通俗易懂]

UVALive 6665 Dragonas Cruller[通俗易懂]

空白部分分别向上下左右移动之后的情况。

如今。给你左右移动的费用ch,上下移动cv。给你一个初始状态(9个数字,当中0代表该空格为空),一个结束状态,问从初始状态移动到结束状态的最小花费。

解题思路:

事实上这道题想法非常easy,简单的bfs + 优先队列。主要是细节处理方面比較麻烦。

把上述九宫格变为一个序列,会发现状态最多就9!种,所以状态能够依照序列的排序离散化。详细參考代码。

然后改成序列之后,会发现左右移动事实上就是 i + 1。 i – 1的操作。上下移动是 i + 3, i – 3 的操作。

代码:

#include<map>
#include<set>
#include<queue>
#include<stack>
#include<cmath>
#include<cstdio>
#include<vector>
#include<string>
#include<fstream>
#include<cstring>
#include<ctype.h>
#include<iostream>
#include<algorithm>
#define maxn 1000
#define INF (1<<30)
#define PI acos(-1.0)
#define mem(a, b) memset(a, b, sizeof(a))
#define For(i, n) for (int i = 0; i < n; i++)
#define debug puts("===============")
const int N = 362881;
typedef long long ll;
using namespace std;
int ch, cv;
int fac[10];
struct node {
    int x, w;
    node(int _x, int _w) {
        x = _x, w = _w;
    }
    bool operator < (const node & T) const {
        return w > T.w;
    }
};
void Atoint(int* a, int &x) {
    int i, j, y;
    x = 0;
    for (i = 0; i < 9; i++) {
        y = a[i];
        for (j = 0; j < i; j++)
            if (a[j] < a[i]) y--;
        x += fac[8 - i] * y;
    }
}
void inttoA(int x, int* a) {
    int has[10] = {0};
    int i, j, y;
    for (i = 0; i < 9; i++) {
        y = x / fac[8 - i];
        for (j = 0; j < 9; j++) if (!has[j]) {
            if (y == 0) break;
            y--;
        }
        a[i] = j, has[j] = 1, x %= fac[8 - i];
    }
}
int st, ed;
priority_queue<node> q;
int d[N], vis[N], a[10], b[10];
void update(int x, int w) {
    if (!vis[x] && d[x] > w) {
        d[x] = w, q.push(node(x, w));
    }
}
void work() {
    Atoint(a, st), Atoint(b, ed);
    while(!q.empty()) q.pop();
    memset(d, 0x7F, sizeof(d));
    memset(vis, 0, sizeof(vis));
    d[st] = 0;
    q.push(node(st, 0));
    int x, w, i, y;
    while(!q.empty()) {
        x = q.top().x, w = q.top().w, q.pop();
        if (vis[x]) continue;
        vis[x] = 1;
        if (x == ed) {
            printf("%d\n", w);
            break;
        }
        inttoA(x, a);
        for (i = 0; i < 9; i++) if (!a[i]) break;
        swap(a[i], a[(i + 1) % 9]);
        Atoint(a, y);
        update(y, w + ch);
        swap(a[i], a[(i + 1) % 9]);
        swap(a[i], a[(i + 8) % 9]);
        Atoint(a, y);
        update(y, w + ch);
        swap(a[i], a[(i + 8) % 9]);
        swap(a[i], a[(i + 3) % 9]);
        Atoint(a, y);
        update(y, w + cv);
        swap(a[i], a[(i + 3) % 9]);
        swap(a[i], a[(i + 6) % 9]);
        Atoint(a, y);
        update(y, w + cv);
    }
}
int main () {
    //freopen("1.txt", "r", stdin);
    fac[0] = 1;
    for (int i = 1; i < 10; i++) fac[i] = fac[i - 1] * i;
    while(scanf("%d%d", &ch, &cv), ch || cv) {
        for (int i = 0; i < 9; i++) scanf("%d", a + i);
        for (int i = 0; i < 9; i++) scanf("%d", b + i);
        work();
    }
    return 0;
}

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/115862.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • java线程池详解及五种线程池方法详解「建议收藏」

    java线程池详解及五种线程池方法详解「建议收藏」基础知识Executors创建线程池Java中创建线程池很简单,只需要调用Executors中相应的便捷方法即可,比如Executors.newFixedThreadPool(intnThreads),但是便捷不仅隐藏了复杂性,也为我们埋下了潜在的隐患(OOM,线程耗尽)。Executors创建线程池便捷方法列表:方法名 功能 newFixedThreadPool(intnThreads) 创建固定大小的线程池 newSingleThreadExecutor()

  • Ubuntu 15.10 安装 Rabbitvcs

    Ubuntu 15.10 安装 Rabbitvcsppa按回车继续或者Ctrl+c取消添加gpg:钥匙环‘/tmp/tmp_70d0zm5/secring.gpg’已建立gpg:钥匙环‘/tmp/tmp_70d0zm5/pubring.gpg’已建立gpg:下载密钥‘34EF4A35’,从hkp服务器keyserver.ubuntu.comgpg:/tmp/tmp_70d0zm5/trustdb.gpg:建立了信任度数据库gpg:密钥34EF4A35:公钥“LaunchpadRabbitVCS”已导入gpg:合计被处理的数量:1g

  • matlab读取txt文件数据_matlab怎么输入数据

    matlab读取txt文件数据_matlab怎么输入数据文件操作是一种重要的输入输出方式,即从数据文件读取数据或将结果写入数据文件。MATLAB提供了一系列低层输入输出函数,专门用于文件操作。1、文件的打开与关闭1)打开文件在读写文件之前,必须先用fopen函数打开或创建文件,并指定对该文件进行的操作方式。fopen函数的调用格式为:fid=fopen(文件名,‘打开方式’)说明:其中fid用于存储文件句柄值,如果返回的句柄值大于0

  • 利用HashSet给list去重[通俗易懂]

    利用HashSet给list去重[通俗易懂]如果有一个string的list要去重,那么可以用以下代码:List<String>orgIds=……..//orgIds即可能存在重复数据的String的集合//利用HashSet去重Set<String>set=newHashSet<String>(orgIds);orgIds=newArrayList<String…

  • springboot框架流程图_java流程框架

    springboot框架流程图_java流程框架这篇介绍springboot的框架流程控制(Controller)层,负责具体的业务模块流程的控制,也就是去拦截客户发来的请求。然后服务(Service)层,负责业务模块的逻辑应用设计,调用DAO层已定义的接口,去实现Service具体的实现类,也就是去和数据库(DAO)层打交道。Dao(serviceImpl)层负责与数据库进行交互设计,用来处理数据的持久化工作,DAO层的数据源配置,以及有关数据库连接的参数都在Spring的配置文件中进行配置。最后一层View层,负责前台h

  • MyBatis-延迟加载与MyBatis缓存(面试题)

    MyBatis-延迟加载与MyBatis缓存(面试题)MyBatis-延迟加载与MyBatis缓存-概念性MyBatis-延迟加载与MyBatis缓存MyBatis-延迟加载与MyBatis缓存-概念性延迟加载(面试题)1、什么是延迟加载(按需加载)2、延迟加载MyBatis缓存(面试题)1、Cache缓存2、MyBatis缓存分析3、一级缓存4、二级缓存原理开启二级缓存5、禁用二级缓存6、刷新二级缓存延迟加载(面试题)1、什么是延迟加载(按需…

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号