UVA-1343 旋转游戏 题解答案代码 算法竞赛入门经典第二版

2023-09-17 02:22:24

GitHub - jzplp/aoapc-UVA-Answer: 算法竞赛入门经典 例题和习题答案 刘汝佳 第二版

题目其实不难，但是耗费了我较多时间。

这种题关键就是在于找到约束条件，我在DFS的基础上，试了很多种策略：

1. 对3种数字，每种数字递归遍历一次，这样每次只需要关注一种数字的变化，情况更少。

2. 使用一个long long类型的数字作为map的key，key表示这种数字在图形中分别的位置，value表示在第几步访问过。如果重复访问且步数更长，则不继续递归。

3. 使用剪枝策略，认为不符合情况结点不继续遍历。（但是我想的剪枝方法不合理，使用了之后是错误的，在最后有给出）

4. 迭代加深搜索，一层一层更深的查找。适用于本题次数最少的要求。

5. 乐观估价函数：在中心每个点的值不对的情况下，每个点都至少需要一次移动才能正确。因此估价函数为 不正确的点数+现有的步数 <= 要求的最大步数。

上述的方法是结合使用的，一开始没想到估价函数，一直在剪枝策略中纠结，然后一直超时。最后换成了估价函数，时间瞬间缩短了。

虽然移动的可能性是无限的，但是最多的移动次数也就是十几次。

AC代码

#include<stdio.h>
#include<map> 
#include<string.h>

#define MAXLEN 15

using namespace std;

int arr[24];
int arrCon[4][7];
// 是否访问过的记录
map<long long, int> mp;
// 记录三种数字完成时的移动情况 
char moves[3][MAXLEN + 5];
// 移动数组的长度 
int moveCount[3];
// 每个移动数组代表的移动类型（可能并不是下表所指示的那个） 
int moveType[3];

// 从输入数据转换为四数组模式 
void convertArr() {
	int i;
	arrCon[0][0] = arr[0]; arrCon[1][0] = arr[1];
	arrCon[0][1] = arr[2]; arrCon[1][1] = arr[3];
	for(i = 0; i < 7; ++i) arrCon[2][i] = arr[4 + i];
	arrCon[0][2] = arr[6]; arrCon[1][2] = arr[8];
	arrCon[0][3] = arr[11]; arrCon[1][3] = arr[12];
	for(i = 0; i < 7; ++i) arrCon[3][i] = arr[13 + i];
	arrCon[0][4] = arr[15]; arrCon[1][4] = arr[17];
	arrCon[0][5] = arr[20]; arrCon[1][5] = arr[21];
	arrCon[0][6] = arr[22]; arrCon[1][6] = arr[23];
}

// 对一个数组移动位置 type->0 往大移动 type->1 往小移动
void moveArr(int *arrSrc, int type) {
	int t, i;
	if(type == 0) {
		t = arrSrc[6];
		for(i = 6; i > 0; --i) arrSrc[i] = arrSrc[i-1];
		arrSrc[0] = t;
	} else {
		t = arrSrc[0];
		for(i = 0; i < 6; ++i) arrSrc[i] = arrSrc[i+1];
		arrSrc[6] = t;
	}
}

// 按照某个方向移动  flag->1 移动 flag->0 恢复移动 
void moveStep(int num, bool flag) {
	bool type;
	switch(num) {
		case 0:
		case 5:
			type = num < 4 ? 1 : 0;
			type = flag ? type : !type;
			moveArr(arrCon[0], type);
			arrCon[2][2] = arrCon[0][2];
			arrCon[3][2] = arrCon[0][4];
			break;
		case 1:
		case 4:
			type = num < 4 ? 1 : 0;
			type = flag ? type : !type;
			moveArr(arrCon[1], type);
			arrCon[2][4] = arrCon[1][2];
			arrCon[3][4] = arrCon[1][4];
			break;
		case 2:
		case 7:
			type = num < 4 ? 0 : 1;
			type = flag ? type : !type;
			moveArr(arrCon[2], type);
			arrCon[0][2] = arrCon[2][2];
			arrCon[1][2] = arrCon[2][4];
			break;
		case 3:
		case 6:
			type = num < 4 ? 0 : 1;
			type = flag ? type : !type;
			moveArr(arrCon[3], type);
			arrCon[0][4] = arrCon[3][2];
			arrCon[1][4] = arrCon[3][4];
			break;
	}
}

// 是否成功 返回成功的字符 否则0 
int isArrive() {
	int num = arrCon[0][2];
	if(arrCon[0][3] != num || arrCon[0][4] != num || arrCon[1][2] != num || arrCon[1][3] != num) 
		return 0;
	if(arrCon[1][4] != num || arrCon[2][3] != num || arrCon[3][3] != num)
		return 0;
	return num;
}

// 根据数字在四数组中的位置，转换为0-27的数字数组 
long long getArrPos(int num) {
	int i, j;
	long long sum = 0;
	for(i = 0; i < 4; ++i) {
		for(j = 0; j < 7; ++j) {
			if(arrCon[i][j] == num) {
				if(i < 2) {
					sum = (sum << 5) + i * 7 + j;
				} else {
					if(j == 2 || j == 4) continue;
					sum = (sum << 5) + i * 7 + j;
				}
			}
		}
	}
	return sum;
}

// 剪枝
bool shouldMove(int num, int step) {
	switch(step) {
		case 0:
			if(arrCon[0][5] == num || arrCon[0][6] == num || arrCon[0][4] == num) return true;
			break;
		case 1:
			if(arrCon[1][5] == num || arrCon[1][6] == num || arrCon[1][4] == num) return true;
			break;
		case 2:
			if(arrCon[2][0] == num || arrCon[2][1] == num || arrCon[2][2] == num) return true;
			break;
		case 3:
			if(arrCon[3][0] == num || arrCon[3][1] == num || arrCon[3][2] == num) return true;
			break;
		case 4:
			if(arrCon[1][0] == num || arrCon[1][1] == num || arrCon[1][2] == num) return true;
			break;
		case 5:
			if(arrCon[0][0] == num || arrCon[0][1] == num || arrCon[0][2] == num) return true;
			break;
		case 6:
			if(arrCon[3][5] == num || arrCon[3][6] == num || arrCon[3][4] == num) return true;
			break;
		case 7:
			if(arrCon[2][5] == num || arrCon[2][6] == num || arrCon[2][4] == num) return true;
			break;
	}
	return false;
}

// 估价函数 true代表有机会 false代表没机会 
bool hvalue(int num, int stepCount, int k) {
	int i, j, value = 0;
	for(i = 0; i < 4; ++i) {
		if(arrCon[i][3] != num) value += 1;
	}
	if(arrCon[0][2] != num) value += 1;
	if(arrCon[0][4] != num) value += 1;
	if(arrCon[1][2] != num) value += 1;
	if(arrCon[1][4] != num) value += 1;
	return stepCount + value < k;
}

//递归寻找 
int getValue(int num, int stepCount, int k) {
	int resArr = isArrive();
	if(resArr) {
		moveType[num - 1] = resArr;
		return stepCount;
	}
	if(stepCount >= k) return 0;
	if(!hvalue(num, stepCount, k))	return 0;
	int i, count, res;
	long long sum; 
	// printf(" ------ %d\n", stepCount);
	for(i = 0; i < 8; ++i) {
		// if(!shouldMove(num, i)) continue;
		// 移动
		moveStep(i, true);
		// printf(" ----------- %d\n", isFind(num));
		sum = getArrPos(num);
		count = mp[sum];
		if(!count || count > stepCount) {
			mp[sum] = stepCount;
			// 记录步骤 
			moves[num-1][stepCount] = i;
			// 访问子节点
			res = getValue(num, stepCount+1, k);
			if(res) {
				// 复位
				moveStep(i, false); 
				return res;
			}
		}
		// 复位
		moveStep(i, false);
	}
	return 0;
}

int getRes(int k) {
	int i, j, mini, minV;
	for(i = 0; i < 3; ++i) {
		mp.clear();
		long long sum = getArrPos(i+1);
		mp[sum] = 0;
		moveCount[i] = getValue(i+1, 0, k);
		if(moveCount[i] > 0) k = moveCount[i];
		// printf("-- %d %d %d \n", k, i, moveCount[i-1]);
		// moves[i-1][moveCount[i-1]] = 0;
	}
	minV = MAXLEN + 10;
	mini = -1;
	for(i = 0; i < 3; ++i) {
		if(moveCount[i] == 0) continue;
		// printf( "[]%d\n", moveCount[i]);
		if(minV > moveCount[i]) {
			minV = moveCount[i];
			mini = i;
		} else if(minV == moveCount[i]) {
			if(strcmp(moves[mini], moves[i]) > 0) {
				minV = moveCount[i];
				mini = i;
			}
		}
	}
	return mini;
}

int main() {
	int i, j, k;
	while(1) {
		if(scanf("%d", &arr[0]) != 1 || arr[0] == 0) break;
		for(i = 1; i < 24; ++i) {
			scanf("%d", &arr[i]);
		}
		convertArr();
		int resType = isArrive();
		if(resType) {
			printf("No moves needed\n");
			printf("%d\n", resType);
			continue;
		}
		for(i = 1; i < MAXLEN; ++i) {
			k = getRes(i);
			if(k >= 0) break;
		}
		if(moveCount[k] == 0) {
			printf("No moves needed\n");
		} else {
			for(i = 0; i < moveCount[k]; ++i) {
				printf("%c", moves[k][i] + 'A');
			}
			putchar('\n'); 
		}
		printf("%d\n", moveType[k]);
	}
	return 0;
}

错误的剪枝策略：（不要使用））

// 错误的剪枝策略，
bool shouldMove(int num, int step) {
	switch(step) {
		case 0:
			if(arrCon[0][5] == num || arrCon[0][6] == num || arrCon[0][4] == num) return true;
			break;
		case 1:
			if(arrCon[1][5] == num || arrCon[1][6] == num || arrCon[1][4] == num) return true;
			break;
		case 2:
			if(arrCon[2][0] == num || arrCon[2][1] == num || arrCon[2][2] == num) return true;
			break;
		case 3:
			if(arrCon[3][0] == num || arrCon[3][1] == num || arrCon[3][2] == num) return true;
			break;
		case 4:
			if(arrCon[1][0] == num || arrCon[1][1] == num || arrCon[1][2] == num) return true;
			break;
		case 5:
			if(arrCon[0][0] == num || arrCon[0][1] == num || arrCon[0][2] == num) return true;
			break;
		case 6:
			if(arrCon[3][5] == num || arrCon[3][6] == num || arrCon[3][4] == num) return true;
			break;
		case 7:
			if(arrCon[2][5] == num || arrCon[2][6] == num || arrCon[2][4] == num) return true;
			break;
	}
	return false;
}

更多推荐

flex:1详解，以及flex:1和flex:auto的区别

什么是flex：1？在css中，我们经常可以看到这样的写法：.box{display:flex;}.item{flex:1;}这里的flex:1相当于flex:110%，它是一个简写属性，表示项目（flexitem）在弹性容器（flexcontainer）中如何伸缩。它相当于flex:110%，包含了三个子属性：fle

JDK动态代理

Java中的两种常用动态代理方式JDK动态代理和Cglib动态代理是Java中常用的实现动态代理的方式。它们都可以在运行时生成代理类，实现对目标对象的代理操作。JDK动态代理适用于接口代理，Cglib动态代理适用于类代理。Cglib动态代理Cglib动态代理是基于继承的动态代理方式。它通过生成目标类的子类来实现代理，子

3.SpringEL方法调用实例

SpringEL方法调用实例文章目录SpringEL方法调用实例介绍SpringEL在注解的形式SpringEL调用List,Map中的方法**从List中过滤元素****从Map中获取值**SpringEL在XML的形式介绍Spring表达式语言(使用SpEL)允许开发人员使用表达式来执行方法和将返回值以注入的方式到

线路板的性能和技术要求有哪些

PCB加工厂家电路板的性能和技术要求与线路板的结构类型、选用的基材有关。不同类型（刚性和挠性）、不同结构（单面、双面、多层、有或无盲孔、埋孔等）、不同基材的PCB板，性能指标是不同的。它的性能等级，与产品设计一样按使用范围通常分为三个等级，PCB厂家描述产品在复杂性、功能性要求的程度和试验、检验的频度的不同。不同性能等

java 单元测试Junit

所谓单元测试，就是针对最小的功能单元，编写测试代码对其进行正确性测试。为了测试更加方便，有一些第三方的公司或者组织提供了很好用的测试框架，给开发者使用。这里介绍一种Junit测试框架。Junit是第三方公司开源出来的，用于对代码进行单元测试的工具（IDEA已经集成了junit框架）。相比于在main方法中测试有如下几个

[设计模式] 浅谈SOLID设计原则

目录单一职责原则开闭原则里氏替换原则接口隔离原则依赖倒转原则SOLID是一个缩写词，代表以下五种设计原则单一职责原则SingleResponsibilityPrinciple,SRP开闭原则Open-ClosedPrinciple,OCP里氏替换原则LiskovSubstitutionPrinciple,LSP接口隔离

华为OD机试真题 Java 实现【路灯照明问题】【2022Q4 100分】，感谢fly晨发现这个问题，并提供更优质的算法

目录专栏导读一、题目描述二、输入描述三、输出描述四、解题思路特别鸣谢：感谢fly晨发现这个问题，并提供更优质的算法。解题思路如下：五、Java算法源码六、效果展示1、输入2、输出3、思路专栏导读本专栏收录于《华为OD机试（JAVA）真题（A卷+B卷）》。刷的越多，抽中的概率越大，每一题都有详细的答题思路、详细的代码注释

模式识别与人工智能（程序与算法）系列讲解 - 总目录

模式识别与人工智能（程序与算法）系列讲解-总目录作者：安静到无声作者简介：人工智能和硬件设计博士生、CSDN与阿里云开发者博客专家，多项比赛获奖者，发表SCI论文多篇。Thanks♪(･ω･)ﾉ如果觉得文章不错或能帮助到你学习，可以点赞👍收藏📁评论📒+关注哦！o(￣▽￣)ｄლ(°◕‵ƹ′◕ლ)希望在传播知识、分享

【算法系列 | 8】深入解析查找算法之—二分查找

序言心若有阳光，你便会看见这个世界有那么多美好值得期待和向往。决定开一个算法专栏，希望能帮助大家很好的了解算法。主要深入解析每个算法，从概念到示例。我们一起努力，成为更好的自己！今天第8讲，讲一下查找算法的二分查找1基础介绍查找算法是很常见的一类问题，主要是将一组数据按照某种规则进行排序。以下是一些常见的查找算法及其应

通过 chatgpt 协助完成网站数据破解

Chatgpt的出现极大地提升了程序员的工作效率，常见的使用场景包括代码自动生成、代码静态检查等，那么chatgpt能否用于某些网站的数据破解工作呢？问题某天线上服务开始报警，原来是某个视频网站无法获取到其cdn地址导致的下载失败问题。经过debug发现原来的明文数据现在变成了加密数据（数据放在html中），如下由于职

Boostrap对HTML的表格的设计和优化

目录01-Bootstrap的默认表格风格02-没有边线-边界的表格03-行与行的背景颜色交替变换(条纹样式)04-给表格加上边框效果05-鼠标移到行上时该行的颜色加深06-把表格的padding值缩减一半,使表格看起来更紧凑07-为表格的行或单元格设置颜色01-Bootstrap的默认表格风格Bootstrap对表格

热文推荐
  1. 如何自动获取短信验证码？

    点击下方关注我，然后右上角点击...“设为星标”，就能第一时间收到更新推送啦~~~这篇文章通过解决实际项目开发中遇到的如何自动获取短信验证码的问题，进一步讲述在Java中如何使用正则。Java中如何使用正则Java中正则相关类位于java.util.regex包下，主要使用2个类，如下：Pattern类：Pattern

  2. tokio::net学习

    tokio::net该模块包含TCP/UDP/Unix网络类型，类似于标准库，可用于实现网络协议。networkingprotocolsOrganizationTcpListenerandTcpStreamprovidefunctionalityforcommunicationoverTCPUdpSocketprovi

  3. 自己实现 SpringMVC 底层机制 系列之-实现任务阶段 7- 完成简单视图解析

    😀前言自己实现SpringMVC底层机制系列之-实现任务阶段7-完成简单视图解析🏠个人主页：尘觉主页🧑个人简介：大家好，我是尘觉，希望我的文章可以帮助到大家，您的满意是我的动力😉😉在csdn获奖荣誉:🏆csdn城市之星2名⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣💓Java全栈群星计

  4. 卷积神经网络中的 Full、Same 和 Valid 卷积

    文章目录卷积神经网络概述Full卷积Same卷积Valid卷积卷积模式的选择代码示例结论🎉欢迎来到AIGC人工智能专栏~卷积神经网络中的Full、Same和Valid卷积☆*o(≧▽≦)o*☆嗨~我是IT·陈寒🍹✨博客主页：IT·陈寒的博客🎈该系列文章专栏：AIGC人工智能📜其他专栏：Java学习路线Java面

  5. 自己实现 SpringMVC 底层机制 系列之-实现任务阶段 4- 完成自定义@Service 注解功能

    😀前言自己实现SpringMVC底层机制系列之-实现任务阶段4-完成自定义@Service注解功能🏠个人主页：尘觉主页🧑个人简介：大家好，我是尘觉，希望我的文章可以帮助到大家，您的满意是我的动力😉😉在csdn获奖荣誉:🏆csdn城市之星2名⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣⁣💓

  6. 多目标优化算法：基于非支配排序的小龙虾优化算法（NSCOA）MATLAB

    一、小龙虾优化算法COA小龙虾优化算法（Crayfshoptimizationalgorithm，COA）由JiaHeming等人于2023年提出，该算法模拟小龙虾的避暑、竞争和觅食行为，具有搜索速度快，搜索能力强，能够有效平衡全局搜索和局部搜索的能力。小龙虾是一种形状类似于虾的甲壳类动物，其甲壳坚硬且颜色丰富。成体的

  7. 深度解析NLP文本摘要技术：定义、应用与PyTorch实战

    目录1.概述1.1什么是文本摘要？1.2为什么需要文本摘要？2.发展历程2.1早期技术2.2统计方法的崛起2.3深度学习的应用2.4文本摘要的演变趋势3.主要任务3.1单文档摘要3.2多文档摘要3.3信息性摘要vs.背景摘要3.4实时摘要4.主要类型4.1抽取式摘要4.2生成式摘要4.3指示性摘要4.4信息性摘要5.抽

  8. Shell脚本中文英文多语言国际化和命令行批处理(bash sh cmd bat)中定义函数的简单写法

    文章目录命令行脚本参考-bat命令行脚本参考-bash值得学习的知识点1.识别终端使用的语言2.函数的编写3.获取用户的输入4.bat文件老是乱码怎么办有时候为了方便别人使用，我们会选择去编写各种各样的命令行脚本：给Windows用户编写.batcmd批处理脚本，给macOS、Linux用户编写.shbashshell

  9. 鼠标、键盘、窗口监听事件

    一、画笔paint//画笔publicclassTestPaint{publicstaticvoidmain(String[]args){newMyPaint().loadFrame();​}}​classMyPaintextendsFrame{​publicvoidloadFrame(){setBounds(200,