首页 > 其他分享 >U455764 The Rotation Game

U455764 The Rotation Game

时间:2025-01-20 18:59:05浏览次数:1  
标签:11 12 15 U455764 17 16 int Game Rotation

U455764 The Rotation Game

题目理解

本题要求移动\(A-H\)中的一列或一行,使其整个一行和一列的数字移动,使最后的中间8个的数字相同。求最少需要移动的步数和它的操纵顺序

思路

1.本题可以很显然的想到用 \(BFS\) 来枚举执行不同字母操作后结果,但每 \(BFS\) 一次就会增加八倍最后肯定会爆队列,因此不可用

2.如果 \(BFS\) 不行那 \(DFS\) 行不行,显然是不行的因为最终答案的操纵次数不会太多,但 \(DFS\) 会将一条路径一直走下去(如一直操纵A,然后B……,若答案在后面,则时间复杂度会超)

3.既然答案的深度不深,且 \(BFS\) 又用不了,那自然会想到迭代加深,一层一层的用 \(DFS\) 遍历即可

实现

1.# 字格的格子按从上到下,从左到右进行编号,在将它每一个操作的对应行或列进行打表,方便后面修改

int op[8][7]={
	{0,2,6,11,15,20,22},     //A
	{1,3,8,12,17,21,23},	 //B
	{10,9,8,7,6,5,4},	 //C
	{19,18,17,16,15,14,13},  //D
	{23,21,17,12,8,3,1},	 //E
	{22,20,15,11,6,2,0},     //F
	{13,14,15,16,17,18,19},  //G
	{4,5,6,7,8,9,10},	 //H
};

2. 在定义一个函数来专门执行每一次的操作

void operate(int x){
	int t=a[op[x][0]];
	for(int i=0;i<6;i++){
		a[op[x][i]]=a[op[x][i+1]];
	}
	a[op[x][6]]=t;
}

3. 因为最后要判断中间的八个数是否相同,因此可以打表将中间八个数编号储存起来;而在 \(DFS\) 中需要回溯,而本题的回溯只需要进行它的逆操作即可(如\(A-F\),\(B-E\))因此需要储存一个逆操作序列。最后再写一个\(check()\)函数来判断中间八个数是否相同。

int cent[8]={6,7,8,11,12,15,16,17};//center
int iop[8]={5,4,7,6,1,0,3,2};
bool check(){
	for(int i=1;i<8;i++){
		if(a[cent[i]]!=a[cent[0]])return false;
	}
	return true;
}

4. 最后的最后,套用迭代加深的模板即可

剪枝:估价函数

因为每一次操作最多使一个点变正确,若现在每一次操作都能修正一个,那最少需要\(8-x\)(\(x\)是目前相同个数最多的数字的个数)步才能完成,若当前的预估次数和已经完成的和大于了当前迭代的深度\(dep\)那在搜索下去没有任何用了,可以直接推出

int f(){
	static int cnt[5];
	memset(cnt,0,sizeof(cnt));
	for(int i=0;i<8;i++){
		cnt[a[cent[i]]]++;
	}
	int k(0);
	for(int i=1;i<=3;i++)k=max(k,cnt[i]);
	return 8-k;
}

最后上完整代码

#include<bits/stdc++.h>
using namespace std;
int op[8][7]={
	{0,2,6,11,15,20,22},     //A
	{1,3,8,12,17,21,23},	 //B
	{10,9,8,7,6,5,4},		 //C
	{19,18,17,16,15,14,13},  //D
	{23,21,17,12,8,3,1},	 //E
	{22,20,15,11,6,2,0},     //F
	{13,14,15,16,17,18,19},  //G
	{4,5,6,7,8,9,10},		 //H
};
int cent[8]={6,7,8,11,12,15,16,17};//center
int iop[8]={5,4,7,6,1,0,3,2};
int dep,a[24],path[110];
void operate(int x){
	int t=a[op[x][0]];
	for(int i=0;i<6;i++){
		a[op[x][i]]=a[op[x][i+1]];
	}
	a[op[x][6]]=t;
}
bool check(){
	for(int i=1;i<8;i++){
		if(a[cent[i]]!=a[cent[0]])return false;
	}
	return true;
}
int f(){
	static int cnt[5];
	memset(cnt,0,sizeof(cnt));
	for(int i=0;i<8;i++){
		cnt[a[cent[i]]]++;
	}
	int k(0);
	for(int i=1;i<=3;i++)k=max(k,cnt[i]);
	return 8-k;
}
bool dfs(int u,int last){
	if(u+f()>dep)return false;
	if(check())return true;
	for(int i=0;i<8;i++){
		if(iop[i]==last)continue;
		operate(i);
		path[u]=i;
		if(dfs(u+1,i))return true;
		operate(iop[i]);
	}
	return false;
}
int main(){
	while(cin>>a[0],a[0]){
		for(int i=1;i<24;i++)cin>>a[i];
		for(dep=0;!dfs(0,-1);dep++);
		if(!dep)cout<<"No moves needed";
		for(int i=0;i<dep;i++){
			cout<<char('A'+path[i]);
		}
		cout<<endl<<a[6]<<endl;
	}
	
}

标签:11,12,15,U455764,17,16,int,Game,Rotation
From: https://www.cnblogs.com/XichenOC/p/18682331

相关文章

  • CF 284B.Cows and Poker Game(Java实现)
    题目分析    奶牛也打扑克。一共有三种情况,简称AFI,并且只有自己为AI状态其余全部人为AF状态才可以亮手牌。思路分析    根据题目分析,针对三个不同状态分析情况:当且仅当有一个I时,唯有这个奶牛可以亮牌,如果I的个数大于1,一个也不能亮牌;当没有I时,判断A的个数,有......
  • [每日 C] MEX Game 1
    前言泻药,吉司机线段树学不动冷静的利用时间已经变成了不冷静的浪费时间,干脆打两道\(\rm{C}\)冷静一下思路看到\(\rm{MEX}\)了,无敌,看到\(2,1,0\)了,无敌但是应该不是这个方向先转化题意\(\textrm{Alice,Bob}\)轮流进行游戏,\(\textrm{Alice}\)每次取......
  • 【论文阅读】GROOT:Learning to Follow Instructions by Watching Gameplay Viedos
    GROOT:LearningtoFollowInstructionsbyWatchingGameplayViedos.作者为北京大学梁一韬所在的TeamCraftJarvis,发表时间为2023Background在开放世界下开发类人级别的具身智能体以解决开放式任务一直是人工智能领域长期以来追求的目标。随着ChatGPT的流行,近年来涌现了一批......
  • (翻译) 关于游戏网络,每个游戏程序需知 What Every Programmer Needs To Know About
    原文链接 https://gafferongames.com/post/what_every_programmer_needs_to_know_about_game_networking/ Haveyoueverwonderedhowmultiplayergameswork?Fromtheoutsideitseemsmagical:twoormoreplayerssharingaconsistentexperience(一致的体验)across......
  • CF1956F Nene and the Passing Game 解题报告
    假设\(j>i\),则:\(i+l_i\lej-l_j,i+r_i\lej-r_j\)所以相当于看区间\([i+l_i,i+r_i]\)和区间\([j-r_j,j-l_j]\)是否有交集可以将这些区间放在数轴上,考虑建虚点,将数轴上的每个点向包含它的区间连边但是这样会有一个问题,记加为右区间,减为左区间,此时就无法判断是哪种区间在相......
  • Beyond Outcomes: Transparent Assessment of LLM Reasoning in Games
    题目超越成果:对LLM游戏推理的透明评估论文地址:https://arxiv.org/abs/2412.13602项目地址:https://visual-ai.github.io/gamebot摘要    大型语言模型(LLM)越来越多地部署在需要复杂推理的现实世界应用中。为了跟踪进展,需要强大的基准来评估它们在表面模式识别......
  • 让我们一起用Pygame Zero 画圆形(空心圆圈、实心圆、多个小球、多层同心圆、随机颜色同
    让我们一起用PygameZero画圆形(空心圆圈、实心圆、多个小球、多层同心圆、随机颜色同心圆、有渐变效果填充圆)本文目录:零、时光宝盒一、绘制空心圆圈二、绘制实心圆三、画多个静止小球四、绘制多层同心圆4.1、绘制5层同心圆4.2、绘制20层同心圆​4.3、绘制条纹相间......
  • RaceGame-Qt游戏项目构建-游戏地图
    RaceGame-Qt游戏项目构建-游戏地图游戏地图概述游戏界面固定为450px*800px;游戏地图由10px*10px像素的方块构成,采用等比缩放记录在一个45*80的array容器中。GameMap相关类GameMap相关类放在gamemap.h头文件中,对应的源文件是gamemap.cpp。一、classGameMa......
  • RaceGame-Qt游戏项目构建-图形界面
    RaceGame-Qt游戏项目构建-图形界面Qt提供了很多图形库,可以直接使用,绘制游戏地图、更新玩家位置,显示操作按钮等。游戏的主体逻辑已经通过Player类和GameMap类实现,只需要根据玩家信息、地图信息,绘制出图形化界面即可。游戏界面概述游戏界面的绘制主要包括:地图/墙体,玩家,操作......
  • RaceGame-Qt游戏项目构建-游戏框架
    RaceGame-Qt游戏项目构建-游戏框架游戏企划使用Qt图形化界面开发一款名为RaceGame的小游戏,游戏玩法是4方玩家(方块)在带有墙体的地图中以一定速度、一定方向前进,碰到墙体会反弹,最终玩家按照到达目的地的先后顺序排名。游戏过程中,玩家可以通过界面上的Button按钮进行释放技能,......