首页 > 其他分享 >2024杭电钉耙2-1003 HDOJ7447 绝对不模拟的简单魔方

2024杭电钉耙2-1003 HDOJ7447 绝对不模拟的简单魔方

时间：2024-07-22 22:19:03浏览次数：10  
标签：钉耙 Cube 魔方 int cmd 杭电 include define

欢迎您来我的网站看这篇题解！

Problem

有一个魔方可能被拧了不超过三次，同时还弄丢了一个角块上的两个贴纸。现在把这两个贴纸贴回去，请问有没有贴错？

只可能拧侧面，不会拧中间层，且每次只能拧 \(90^\circ\)。

魔方用一个 9 行 12 列的字符型矩阵表示：

输入格式

初始魔方的展开图如下图：

初始魔方展开图

\(1\le T\le 10\)

Solution

说实话没啥好考虑的，可能有取巧的方法？但是我不太想思考。

定义一个魔方类 Cube，包含了一个二维字符数组。只需要写六个成员函数（对应六种旋转操作），就可以描述这个魔方的所有旋转情况。

然后进行 dfs 搜索每一种可能的情况，并且与初始魔方展开图进行比较。

如果当前状态与展开图对比，不同的字符不超过两个，则说明复原成功。

  • 如果完全相同，则没有贴错，输出 No problem。
  • 如果有两个不相同，则贴错了，输出错误角块对应的三个数字。

没啥好多说的。Talk is cheap.Show me the code.

Code

/**************************************************************
 * Problem: 
 * Author: Vanilla_chan
 * Date: 
 * E-Mail: [email protected]
 **************************************************************/
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<string>
#include<cstring>
#include<cmath>
#include<map>
#include<set>
#include<queue>
#include<vector>
#include<limits.h>
#define IL inline
#define re register
#define LL long long
#define ULL unsigned long long
#ifdef TH
#define debug printf("Now is %d\n",__LINE__);
#else
#define debug
#endif
#ifdef ONLINE_JUDGE
char buf[1<<23],* p1=buf,* p2=buf,obuf[1<<23],* O=obuf;
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
#endif
using namespace std;

#define pii pair<int,int>
#define mk(a,b) make_pair(a,b)
/*
***111******
***111******
***111******
222333444555
222333444555
222333444555
***666******
***666******
***666******
*/

#define N 1000
struct Cube
{
	string str[20];
	Cube()
	{
		for(int i=0;i<20;i++) str[i]="!!!!!!!!!!!!!!!!";
		str[0]="***111******";
		str[1]="***111******";
		str[2]="***111******";
		str[3]="222333444555";
		str[4]="222333444555";
		str[5]="222333444555";
		str[6]="***666******";
		str[7]="***666******";
		str[8]="***666******";
		
	}
	void output()
	{
		for(int i=0;i<9;i++) cout<<str[i]<<endl;
		cout<<endl;
	}
	void top()
	{
//		debug
		str[3]=str[3].substr(3,9)+str[3].substr(0,3);
		string ss[20];
		int mp[9][4]={1,4,1,5,1,5,1,6,1,6,2,6,2,6,3,6,3,6,3,5,3,5,3,4,3,4,2,4,2,4,1,4};
		for(int i=0;i<9;i++) for(int j=0;j<4;j++) mp[i][j]--;
		for(int t=0;t<2;t++)
		{
//			debug
			for(int i=0;i<9;i++) ss[i]=str[i];
			for(int k=0;k<8;k++)
			{
//				debug
				str[mp[k][2]][mp[k][3]]=ss[mp[k][0]][mp[k][1]];
			}
		}
	}
	void down()
	{
		str[5]=str[5].substr(3,9)+str[5].substr(0,3);
		string ss[20];
		int mp[9][4]={7,4,7,5,7,5,7,6,7,6,8,6,8,6,9,6,9,6,9,5,9,5,9,4,9,4,8,4,8,4,7,4};
		for(int i=0;i<9;i++) for(int j=0;j<4;j++) mp[i][j]--;
		for(int t=0;t<2;t++)
		{
			for(int i=0;i<9;i++) ss[i]=str[i];
			for(int k=0;k<8;k++)
			{
				str[mp[k][0]][mp[k][1]]=ss[mp[k][2]][mp[k][3]];
			}
		}
	}
	void right()
	{
		string ss[20];
		int mp[9][4]={4,7,4,8,4,8,4,9,4,9,5,9,5,9,6,9,6,9,6,8,6,8,6,7,6,7,5,7,5,7,4,7};
		for(int i=0;i<9;i++) for(int j=0;j<4;j++) mp[i][j]--;
		for(int i=0;i<9;i++) ss[i]=str[i];
		for(int t=0;t<2;t++)
		{
			for(int i=0;i<9;i++) ss[i]=str[i];
			for(int k=0;k<8;k++)
			{
				str[mp[k][0]][mp[k][1]]=ss[mp[k][2]][mp[k][3]];
			}
		}
		
		for(int i=11;i>=3;i--) str[i][5]=str[i-3][5];
		
		int mp1[9][4]={4,10,3,6,5,10,2,6,6,10,1,6};
		memcpy(mp,mp1,sizeof(mp));
		for(int i=0;i<3;i++) for(int j=0;j<4;j++) mp[i][j]--;
		for(int i=0;i<20;i++) ss[i]=str[i];
		for(int k=0;k<3;k++)
		{
			str[mp[k][2]][mp[k][3]]=ss[mp[k][0]][mp[k][1]];
		}
		
		int mp2[9][4]={10,6,6,10,11,6,5,10,12,6,4,10};
		memcpy(mp,mp2,sizeof(mp));
		for(int i=0;i<3;i++) for(int j=0;j<4;j++) mp[i][j]--;
		for(int i=0;i<20;i++) ss[i]=str[i];
		for(int k=0;k<3;k++)
		{
			str[mp[k][2]][mp[k][3]]=ss[mp[k][0]][mp[k][1]];
		}
	}
	void left()
	{
		string ss[20];
		int mp[9][4]={4,1,5,1,5,1,6,1,6,1,6,2,6,2,6,3,6,3,5,3,5,3,4,3,4,3,4,2,4,2,4,1};
		for(int i=0;i<9;i++) for(int j=0;j<4;j++) mp[i][j]--;
		for(int i=0;i<9;i++) ss[i]=str[i];
		for(int t=0;t<2;t++)
		{
			for(int i=0;i<9;i++) ss[i]=str[i];
			for(int k=0;k<8;k++)
			{
				str[mp[k][0]][mp[k][1]]=ss[mp[k][2]][mp[k][3]];
			}
		}
		for(int i=11;i>=3;i--) str[i][3]=str[i-3][3];
		
		int mp1[9][4]={4,12,3,4,5,12,2,4,6,12,1,4};
		memcpy(mp,mp1,sizeof(mp));
		for(int i=0;i<3;i++) for(int j=0;j<4;j++) mp[i][j]--;
		for(int i=0;i<20;i++) ss[i]=str[i];
		for(int k=0;k<3;k++)
		{
			str[mp[k][2]][mp[k][3]]=ss[mp[k][0]][mp[k][1]];
		}
		
		int mp2[9][4]={10,4,6,12,11,4,5,12,12,4,4,12};
		memcpy(mp,mp2,sizeof(mp));
		for(int i=0;i<3;i++) for(int j=0;j<4;j++) mp[i][j]--;
		for(int i=0;i<20;i++) ss[i]=str[i];
		for(int k=0;k<3;k++)
		{
			str[mp[k][2]][mp[k][3]]=ss[mp[k][0]][mp[k][1]];
		}
	}
	
	void front()
	{
		string ss[20];
		int mp[20][4]={4,4,5,4,5,4,6,4,6,4,6,5,6,5,6,6,6,6,5,6,5,6,4,6,4,6,4,5,4,5,4,4};
		for(int i=0;i<8;i++) for(int j=0;j<4;j++) mp[i][j]--;
		for(int i=0;i<9;i++) ss[i]=str[i];
		for(int t=0;t<2;t++)
		{
			for(int i=0;i<9;i++) ss[i]=str[i];
			for(int k=0;k<8;k++)
			{
				str[mp[k][2]][mp[k][3]]=ss[mp[k][0]][mp[k][1]];
			}
		}
		int mp1[30][4]={4,7,3,4,3,4,6,3,6,3,7,6,7,6,4,7,5,7,3,5,3,5,5,3,5,3,7,5,7,5,5,7,6,7,3,6,3,6,4,3,4,3,7,4,7,4,6,7};
		memcpy(mp,mp1,sizeof(mp));
		for(int i=0;i<12;i++) for(int j=0;j<4;j++) mp[i][j]--;
		for(int i=0;i<9;i++) ss[i]=str[i];
		for(int t=0;t<1;t++)
		{
			for(int i=0;i<9;i++) ss[i]=str[i];
			for(int k=0;k<12;k++)
			{
				str[mp[k][2]][mp[k][3]]=ss[mp[k][0]][mp[k][1]];
			}
		}
	}
	
	void back()
	{
		string ss[20];
		int mp[20][4]={4,10,5,10,5,10,6,10,6,10,6,11,6,11,6,12,6,12,5,12,5,12,4,12,4,12,4,11,4,11,4,10};
		for(int i=0;i<8;i++) for(int j=0;j<4;j++) mp[i][j]--;
		for(int i=0;i<9;i++) ss[i]=str[i];
		for(int t=0;t<2;t++)
		{
			for(int i=0;i<9;i++) ss[i]=str[i];
			for(int k=0;k<8;k++)
			{
				str[mp[k][2]][mp[k][3]]=ss[mp[k][0]][mp[k][1]];
			}
		}
		int mp1[20][4]={4,9,1,4,1,4,6,1,6,1,9,6,9,6,4,9,5,9,1,5,1,5,5,1,5,1,9,5,9,5,5,9,6,9,1,6,1,6,4,1,4,1,9,4,9,4,6,9};
		memcpy(mp,mp1,sizeof(mp));
		for(int i=0;i<12;i++) for(int j=0;j<4;j++) mp[i][j]--;
		for(int i=0;i<9;i++) ss[i]=str[i];
		for(int t=0;t<1;t++)
		{
			for(int i=0;i<9;i++) ss[i]=str[i];
			for(int k=0;k<12;k++)
			{
				str[mp[k][2]][mp[k][3]]=ss[mp[k][0]][mp[k][1]];
			}
		}
	}
	
};

bool found=0;


map<pii,string>out;


void check(Cube cube)
{
	Cube ans;
	int diff=0;
	pii pos;
	for(int i=0;i<9;i++)
	{
		for(int j=0;j<12;j++)
		{
			if(cube.str[i][j]!=ans.str[i][j])
			{
				diff++;
				pos=make_pair(i,j);
			}
		}
	}
	pos.first++;
	pos.second++;
	if(diff==0||diff==2)
	{
		found=1;
		if(diff)
		{
			cout<<out[pos]<<endl;
		}
		else
		{
			cout<<"No problem"<<endl;
		}
	}
}
void dfs(int depth,Cube cube)
{
	if(found) return;
	check(cube);
	if(found) return;
	if(depth>=3) return;
	Cube nxt;
	
	for(int i=0;i<=1;i++)
	{
		int t=i?1:3;
		nxt=cube;
		while(t--) nxt.front();
		dfs(depth+1,nxt);
		
		t=i?1:3;
		nxt=cube;
		while(t--) nxt.back();
		dfs(depth+1,nxt);
		
		t=i?1:3;
		nxt=cube;
		while(t--) nxt.left();
		dfs(depth+1,nxt);
		
		t=i?1:3;
		nxt=cube;
		while(t--) nxt.right();
		dfs(depth+1,nxt);
		
		t=i?1:3;
		nxt=cube;
		while(t--) nxt.top();
		dfs(depth+1,nxt);
		
		t=i?1:3;
		nxt=cube;
		while(t--) nxt.down();
		dfs(depth+1,nxt);
	}
	
	
}

int main()
{
	out[mk(4,3)]=out[mk(4,4)]=out[mk(3,4)]="1 2 3";
	out[mk(1,4)]=out[mk(4,1)]=out[mk(4,12)]="1 2 5";
	out[mk(1,6)]=out[mk(4,9)]=out[mk(4,10)]="1 4 5";
	out[mk(3,6)]=out[mk(4,6)]=out[mk(4,7)]="1 3 4";
	out[mk(6,1)]=out[mk(9,4)]=out[mk(6,12)]="2 5 6";
	out[mk(6,3)]=out[mk(6,4)]=out[mk(7,4)]="2 3 6";
	out[mk(6,6)]=out[mk(6,7)]=out[mk(7,6)]="3 4 6";
	out[mk(9,6)]=out[mk(6,9)]=out[mk(6,10)]="4 5 6";
	
	
	
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cout.precision(10);
	
//	Cube test;
//	test.str[0]="***123******";
//	while(1)
//	{
//		string cmd;cin>>cmd;
//		if(cmd=="left") test.left();
//		if(cmd=="right") test.right();
//		if(cmd=="down") test.down();
//		if(cmd=="top") test.top();
//		if(cmd=="back") test.back();
//		if(cmd=="front") test.front();
//		test.output();
//	}
	
	
	int t=1;
	cin>>t;
	while(t--)
	{
		found=0;
		Cube cube;
		for(int i=0;i<9;i++) cin>>cube.str[i];
		dfs(0,cube);
		
	}
	return 0;
}

标签：钉耙,Cube,魔方,int,cmd,杭电,include,define
From： https://www.cnblogs.com/Vanilla-chan/p/18317096

相关文章

  • 2024“钉耙编程”中国大学生算法设计超级联赛（2）
    Preface最唐氏的一集，前中期被A卡得数次破防红温，后期经典不知道在干嘛摆着摆着就结束了可惜的是徐神最后1h写的B因为两个数组搞反了一直没过，赛后看了眼就过了，这下狠狠地掉Rating了鸡爪丁真构造题，但有人连WA三发怎么回事呢首先不难想到最大化和\(1\)连边的数量，首......
  • 2024杭电1003 HDOJ7435 树
    本文同步发布于我的网站Problem给一棵根为1的有根树，点\(i\)具有一个权值\(A_i\)。定义一个点对的值\(f(u,v)=\max\left(A_u,A_v\right)\times\left|A_u-A_v\right|\)。你需要对于每个节点\(i\)，计算\(ans_i=\sum_{u\in\operatorname{subtree}(i),v\in\op......
  • 2024“钉耙编程”中国大学生算法设计超级联赛（1）结题报告1 2 8
    1001循环位移字符串哈希将a展开*2对于每个长度为len_a的序列进行一次hash存储并将其插入set中对于b进行一次哈希对于每个长度为len_a的连续子串进行一次查询点击查看代码#include<bits/stdc++.h>usingnamespacestd;//22222constintN=5e6+10;constintp1......
  • 2024“钉耙编程”中国大学生算法设计超级联赛（1）
    发挥相当差，最好笑的是1h没写出一个三维偏序、30min没写出一个字符串哈希。甚至1h没意识到组合数式子推错了。A我写了点阴间东西。假设模式串为ABC，考虑一个形如ABCABCABC的东西，如果长度是\(x\)，会贡献\(x-n+1\)个子串。枚举\(i\)，从\(i\)把\(T\)分成两部分，一部分......
  • 2024杭电第一场
    1012并考虑两维坐标都离散化后枚举每个格子，用二维前缀和计算其被覆盖的次数，设为cnt则k固定时该格子的贡献为：(1-C[n-cnt][k]/C[n][k])*该格子的面积注意事项：1.处处取模2.给的是点坐标，不是格点坐标，因此计算二维前缀和时要x++,y++#include<bits/stdc++.h>usingnames......
  • 循环位移（2024“钉耙编程”中国大学生算法设计超级联赛（1））
    #include<bits/stdc++.h>#defineendl'\n'usingll=longlong;typedefunsignedlonglongull;usingnamespacestd;voidGordenGhost();constintN=4e6+7;constintP=131;ullp[N],an[N],bn[N];intn;voidinit(stringa,stringb){......
  • 2024“钉耙编程”中国大学生算法设计超级联赛（1）
    Preface唐完了的一集，被前中期题花式腐乳以至于中期一度被同校队伍打出\(n+3\)最后4h时堪堪写完8个题，最后1h冲刺众数那个题然后写一半方法假了直接下班当然还有个难绷的是传送那个题和我今年给新生拉的数据结构专题的一个题几乎一样，把代码拉来改下输入输入就过了，12min抢......
  • 杭电多校补题
    1001.循环位移#include<bits/stdc++.h>usingnamespacestd;typedefunsignedlonglongull;constintN=1048580*2;constintP=131;ullp[N],h1[N],h2[N];voidsolve(){stringa,b;cin>>a>>b;intn=a.size()......
  • 2021杭电多校10 D.Pty hates prime numbers题解
    前言暑期第三次组队赛是选的21年杭电多校10，遗憾爆0，被对面队打爆，赛后狠狠补题。这道题的题解，以及网上搜到的其他题解看了好久没看懂，在问了队里大腿多次后，总算磨出来了，这里讲一下我的理解。题意多次询问，每次给定\(n\)和\(k\)，如果一个数的质因数里包括前\(k\)个质数，则这个数......
  • C++课程设计杭电题目(中）
    2073.无限的路题目描述http://acm.hdu.edu.cn/showproblem.php?pid=2073http://acm.hdu.edu.cn/showproblem.php?pid=2073ProblemDescription甜甜从小就喜欢画图画，最近他买了一支智能画笔，由于刚刚接触，所以甜甜只会用它来画直线，于是他就在平面直角坐标系中画出如下的图形：......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99