题目链接:
http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=2139
类型: 隐式图搜索, BFS, 哈希判重,模拟
原题:
Digits like to dance. One day, 1, 2, 3, 4, 5, 6, 7 and 8 stand in a line to have a wonderful party. Each time, a male digit can ask a female digit to dance with him, or a female digit can ask a male digit
to dance with her, as long as their sum is a prime. Before every dance, exactly one digit goes to who he/she wants to dance with - either to its immediate left or immediate right.
For simplicity, we denote a male digitxby itselfx, and denote a female digitxby -x. Suppose the digits are in order {1, 2, 4, 5, 6, -7, -3, 8}. If -3 wants to dance
with 4, she must go either to 4's left, resulting {1, 2, -3, 4, 5, 6, -7, 8} or his right, resulting {1, 2, 4, -3, 5, 6, -7, 8}. Note that -3 cannot dance with 5, since their sum 3+5=8 is not a prime; 2 cannot dance with 5, since they're both male.
Given the initial ordering of the digits, find the minimal number of dances needed for them to sort in increasing order (ignoring signs of course).
Input
The input consists of at most 20 test cases. Each case contains exactly 8 integers in a single line. The absolute values of these integers form a permutation of {1, 2, 3, 4, 5, 6, 7, 8}. The last case is
followed by a single zero, which should not be processed.
Output
For each test case, print the case number and the minimal number of dances needed. If they can never be sorted in increasing order, print -1.
Sample Input
1 2 4 5 6 -7 -3 8
1 2 3 4 5 6 7 8
1 2 3 5 -4 6 7 8
1 2 3 5 4 6 7 8
2 -8 -4 5 6 7 3 -1
0
Output for the Sample Input
Case 1: 1
Case 2: 0
Case 3: 1
Case 4: -1
Case 5: 3
题目大意:
数字喜欢跳舞。 一天,1,2,3,4,5,6,7,8站在一排准备跳舞。数字也有男女之别, 正数代表男性, 负数代表女性。每一次,男性数字可以邀请任何一个女性数字和他跳舞, 当然女性数字也可以任意一个男性数字一起跳舞。 前提是男女的数字之和(都是绝对值)是一个素数。也可以和他(她)相邻的数字一起跳舞,不管对方是男还是女。
假设初始排列为{1, 2, 4, 5, 6, -7, -3, 8}, 如果-3想和4一起跳舞,那么-3就必须走到4的左边和右边, 如果在左边那么排列变为:{1, 2, -3, 4, 5, 6, -7, 8} ,
如果在右边那么排列变为{1, 2, 4, -3, 5, 6, -7, 8}.
问题是给一个初始排列,找到一个最小的邀请跳舞次数,使得它们的排列变成是升序的(按绝对值)。如果不可能,输出-1.
分析与总结:
这题有点恶心了,应该是我的解法比较挫,直接模拟状态转换的过程,然后得到新的排列状态。模拟过程需要注意的是,邀请的对方是在自己位置的左边还是右边。
只要细心一点基本没问题。
就是因为错了一个小小的字母而RE了好几次,都是粗心惹的祸, 郁闷。。。
/*
* UVa 11198 - Dancing Digits
* 隐式图搜索,BFS
* Time: 0.740s (UVa)
* Author: D_Double
*/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
using namespace std;
typedef int State[8];
const int HashSize = 1000003;
State start;
State que[50000];
int head[HashSize], next[HashSize], step[50000], ans;
int prime[] = {0,0,1,1,0,1,0,1,0,0,0,1,0,1,0,0,0,1};
inline void init_lookup_table(){
ans = -1; step[0] = 0;
memset(head, 0, sizeof(head));
}
inline int hash(State &s){
int v=0;
for(int i=0; i<8; ++i) v = v*10 + abs(s[i]);
return (v & 0x7FFFFFFF) % HashSize;
}
inline bool try_to_insert(int s){
int h = hash(que[s]);
int u = head[h];
while(u){
if(memcmp(que[u], que[s], sizeof(que[s]))==0) return false;
u = next[u];
}
next[s] = head[h];
head[h] = s;
return true;
}
bool is_ok(State &s){
for(int i=0; i<7; ++i) if(abs(s[i]) > abs(s[i+1])) return false;
return true;
}
// 邀请跳舞之后的排列转化
void goto_dance(State &s, int u, int v, int dir){
if(dir==1){ //左边
if(u==v-1) return; // 如果本来就在他的左边,不移动
if(u==v+1){ // 如果再它右边,直接交换
int tmp = s[u]; s[u]=s[v]; s[v] = tmp;
}
int t = s[u];
if(u>v){
for(int i=u; i>v; --i) s[i] = s[i-1];
s[v] = t;
}
else{
for(int i=u; i<v-1; ++i) s[i] = s[i+1];
s[v-1] = t;
}
}
else{ // 右边
if(u==v+1) return ; //如果本来就在他右边, 不移动
if(u==v-1){
int tmp = s[u]; s[u]=s[v]; s[v] = tmp;
}
int t = s[u];
if(u>v){
for(int i=u; i>v+1; --i) s[i] = s[i-1];
s[v+1] = t;
}
else{
for(int i=u; i<v; ++i) s[i] = s[i+1];
s[v] = t;
}
}
}
void bfs(){
init_lookup_table();
int front = 0, rear = 1;
memcpy(que[0], start, sizeof(start));
try_to_insert(0);
while(front < rear){
State &s = que[front];
if(is_ok(s)){
ans = step[front]; return ;
}
for(int i=0; i<8; ++i){
for(int j=0; j<8; ++j)if(i!=j && (s[i]>0&&s[j]<0 || s[i]<0&&s[j]>0) ){
int sum = abs(s[i])+abs(s[j]);
if(!prime[sum]) continue;
// 移动到目标左边或右边:
for(int k=1; k<=2; ++k){
State &t = que[rear];
memcpy(t, s, sizeof(s));
goto_dance(t, i, j, k);
if(try_to_insert(rear)){
step[rear] = step[front]+1; ++rear;
}
}
}
}
++front;
}
}
int main(){
int cas = 1;
while(scanf("%d",&start[0]), start[0]){
for(int i=1; i<8; ++i) scanf("%d", &start[i]);
bfs();
printf("Case %d: %d\n",cas++, ans);
}
return 0;
}
—— 生命的意义,在于赋予它意义。
分享到:
相关推荐
uva 11198 - Dancing Digits.cpp 的代码
北大POJ3373-Changing Digits【DFS+强剪枝】 解题报告+AC代码
北大POJ3733-Changing Digits【DFS+强剪枝】 解题报告+AC代码
Laravel开发-unique-digits 为PHP的不同需求(票号和其他)创建数字值。
开源项目-dghubble-go-digits.zip,Go packages for Digits - make a phone number login app in ~100 lines
本代码为自制:自动获取时间戳10位10进制,亲测可运行。
上机测试-数科20-digits.py
以C51为主采用74HC573进行proteus仿真,可实现六位(可调)数字右闪输出,输出结果显示在数码管上
Digits.com的Cordova插件 安装 cordova plugin add https://github.com/cosmith/cordova-digits.git --variable FABRIC_API_KEY=your_api_key --variable FABRIC_API_SECRET=your_api_secret 用法 目前仅实现一种...
“#t-mobile-digits”
手写数字识别数据集,MNIST,包括原始数据集的所有样本,以及抽取的2000个样本的子集,.mat格式。美国著名数据集NIST的子集,模式识别常用实验数据集
Gray-scale-Hand-Written-Digits-Pytorch 手写数字识别Mnist的Pytorch实现 博客: 一、引言(Introduction) 手写数字识别时经典的图像分类任务,也是经典的有监督学习任务,经常被用于测试图像的特征提取效果、...
iOS 4位数字密码-Swift 2.0 iOS的4位数字别针用户界面
PFUser-Digits:使用Twitter Digits验证解析用户
python版多数字标注识别
或者,您可以转到Project-on-Handwriting-Digits-Recognition / 3.-Run-Algorithms-on-the-Data目录,以了解我们如何在数据上实现不同的算法。 由于该项目基于特定的手写数字数据集,因此“ 2.3.-Matlab编写的数据...
Anaconda 4.10.3 Tensorflow 2.6.0 python3.7.8 1、将图片通过opencv切割识别定位车牌,切割保存 2、识别省份简称、识别城市代号、识别车牌编号 ...python train-license-digits.py predict 进行车牌编号识别
贝叶斯,Fisher线性判别实现手写数字识别
mnist_digits.7z 每个文件是一个数字的01矩阵,一个文件对应一个数字,文件名第一个字符为对应的数字。 无须积分
二摘代码MATLAB 实施随机森林 在这个项目中,我们有两种基于MATLAB的随机森林实现,带有预处理和不带有预处理。 源代码显示在文件夹中。 如何运行代码 RandomForest.m是执行随机森林过程的主要文件,通过该文件,...