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)
blank

相关推荐

  • matlab声源定位算法实现_MATLAB程序

    matlab声源定位算法实现_MATLAB程序这是通过传统互相关的方法来进行声源定位的程序,做完互相关之后,红色标注的程序行,应该如何理解呢,是通过什么方法来实现最终延迟差的估计的呢?clclearallcloseall%%%*各参数设置*%–声源相关参数fm=2000;%Hz:信源调频信号最高频率周期0.5msTs=0.2;%s:信源周期0.2s%–采样和信号处理相关参数fs=10*fm;%采样率…

  • 从零开始学习Android开发[通俗易懂]

    从零开始学习Android开发[通俗易懂]1.首先有一点点JAVA的基础知识建议阅读:https://www.runoob.com/java/java-basic-syntax.html讲的比较细,只看到高阶之前即可。2.推荐《第一行代码:Android(第2版)》第一行代码第二版,被Android开发者誉为“Android学习第一书”。全书系统全面、循序渐进地介绍了Android软件开发的必备知识、经验和技巧。…

  • 计算机教育中缺失的一课,劝学弟学妹们一句,一定要趁早补上,工作后会事半功倍!「建议收藏」

    计算机教育中缺失的一课,劝学弟学妹们一句,一定要趁早补上,工作后会事半功倍!「建议收藏」各位学弟学妹们好,作为稍微年长的我(岁月是把杀猪刀啊),今天就给大家补补课。在大学里的,我们上的计算机专业课程一般都是像操作系统、编译原理、计算机组成原理、计算机网络这些理论课程,还有一些像C语言、Java、.Net这些可以实践的课程,甚至还有可能让你焊一个收音机,但是对于一些基本习惯却很容易被忽略,需要学弟学妹们自行摸索。实际上,一些好的基本习惯是时时刻刻在影响着我们自己的,不仅是在学校的学习生活中,还是在毕业后的工作生活中。今天我要给大家说就是,使用键盘的习惯。有的同学可能会诧异,键盘谁不会用啊,

  • linux 删除 软连接(shell创建软连接)

    语法ln(选项)源文件目标文件1、区分符号连接“源文件”可以是文件或者目录硬连接,“源文件”参数只能是文件2、创建软链接ln–s/source/target参数:-s或——symbolic:对源文件建立符号连接,而非硬连接;3、删除软连接rm–rf/target注意:不要在后文件名后面加斜杆“/”否则会删除文件夹的内容参考:ht…

  • Hadoop 查看某个文件分成几个块,分别在那台机架的哪个机器上「建议收藏」

    Hadoop 查看某个文件分成几个块,分别在那台机架的哪个机器上「建议收藏」Hadoop 查看某个文件分成几个块,分别在那台机架的哪个机器上

  • cas算法是什么_对算法的认识

    cas算法是什么_对算法的认识应用原子操作类,例如AtomicInteger,AtomicBoolean …适用于并发量较小,多cpu情况下;Java中有许多线程安全类,比如线程安全的集合类。从Java5开始,在java.util.concurrent包下提供了大量支持高效并发访问的集合接口和实现类。如:ConcurrentMap、ConcurrentLinkedQueue等线程安全集合。引入问题那么问题来了,这些线程安全类的底层是怎么保证线程安全的,你可能会想到是不是使用同步代码锁synchronized?引入概念这些线

发表回复

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

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