2333. Bridged Marble Rings
单点时限: 2.0 sec
内存限制: 256 MB
26 marbles―half yellow and half gray―are distributed between two circles of 13 marbles each. The marbles in each circle can be freely rotated clockwise or counterclockwise. The upper and lower circles are bridged by a smaller circle, which rotates―in the plane of the board―180 degrees, effectively exchanging the three bottommost marbles of the upper circle with the three uppermost marbles of the lower one. The goal is to get all gray marbles to the upper circle and all yellow marbles to the lower one while minimizing the number of times the bridging circle is rotated.
输入格式
The input is a series of lines, where each line describes an initial board configuration. Each line is a permutation of 13 y’s and 13 g’s. The first half of the line describes the clockwise configuration of the upper circle, and the rest of the line describes the clockwise configuration of the lower one. Of course, each y corresponds to a yellow marble, and each g corresponds to a gray one. The input file will include multiple test cases. Each test case consists of a single line containing some permutation of the string y13g13. All lines (including the last one) are terminated with a newline. The newline immediately follows the last letter on the line.
输出格式
For each input case, you should print the minimum number of bridge rotations on a single line.
样例
input
gggggggggggggyyyyyyyyyyyyy
yyyyyggggggggyyyygggggyyyy
gyyygyggyyygyyggyyggggyygg
ygygygygygygygygygygygygyg
output
0
2
5
6
复盘： 一开始完全没有思路，搜索了一下题目，在hchlqlz这里看到了bfs，大致上的思路有了，自底向上地遍历每个位置，每次共13*13种交换方式，写了个getRotateStr。
接着发现运行很慢，第二个样例就运行缓慢了。想到上下环都可以旋转于是写了rotateSame和ismarked两个函数，进一步剪枝，然后发现前两个样例能过，第三个也能过，但是运行还是缓慢。
于是仔细看了看上面链接的代码，发现如下亮点：
1、由于字符串单一，仅仅两种字符，直接使用1,0来代替‘g’与‘y’，由于一共26位，int 32位，一半正数31位，完全够。
2、由于上下环都能旋转，使用两个环的最小值来定位每个状态。
3、通过两层循环旋转上下环，然后固定交换高位的三位来实现上下环的交换。
4、自顶向下bfs，搜索出所有的状态对应的最小交换次数。我觉得这么做的原因可能有这么几点：①需要多次的回答答案②答案数一定，13位1和13位0的排列组合有限，同时还需要去掉那些旋转后仍然相同的状态③每次自底向上搜索，会做很多重复的工作。
具体写的时候，掌握了|，&，<<,>>运算符的使用。写v2.0时，在两层循环旋转上下环时，一开始对变量的作用有点理解错了，想少定义两个变量，困住好久，然后发现不对劲，接着在改的时候不小心重定义了a，导致后续debug了好久，终于找到错误点。v3.0的exchange_NotFix函数也因为觉得因为类似的省两个变量的原因，导致程序没能按预想的运行。
v1.0直接字符串处理，运行缓慢，超时
#include<iostream>
#include<queue>
#include<unordered_map>
using namespace std;
string getRotateStr(string s,int a,int b){
string ans=s;
for(int i=0;i<3;i++){
a=a%13;
b=b%13+13;
char tmp=ans[a];
ans[a]=ans[b];
ans[b]=tmp;
a++;
b++;
}
return ans;
}
bool rotateSame(unordered_map<string,int> &mark,string s){
bool ans=false;
for(int i=0;i<s.size();i++){
string tmpstring=s.substr(i)+s.substr(0,i);
if(mark[tmpstring]){
ans=true;
break;
}
}
return ans;
}
bool ismarked(unordered_map<string,int> &markup,unordered_map<string,int> &marklow,string s){
bool up=rotateSame(markup,s.substr(0,13));
bool low=rotateSame(marklow,s.substr(13,13));
return up&&low;
}
int main(){
string s,rights="gggggggggggggyyyyyyyyyyyyy";
s.resize(26);
unordered_map<string,int> yes;
yes[rights]=1;
while(scanf("%s",&s[0])!=EOF){
int findans=0;
unordered_map<string,int> markup;
unordered_map<string,int> marklow;
if(yes[s]){
cout<<0<<endl;
continue;
}
queue<pair<string,int>> q;
q.push(make_pair(s,0));
markup[s.substr(0,13)]++;
marklow[s.substr(13,13)]++;
while(!q.empty()){
pair<string,int> tmpNode = q.front();
q.pop();
string tmps=tmpNode.first;
int times=tmpNode.second;
for(int i=0;i<13;i++){
for(int j=0;j<13;j++){
string nextStatus=getRotateStr(tmps,i,j);
if(!ismarked(markup,marklow,nextStatus)){
markup[nextStatus.substr(0,13)]++;
marklow[nextStatus.substr(13,13)]++;
if(yes[nextStatus]){
findans=1;
cout<<(times+1)<<endl;
break;
}
q.push(make_pair(nextStatus,times+1));
}
}
if(findans)break;
}
if(findans)break;
}
}
}
v2.0参考hchlqlz的思路。AC了。
#include<iostream>
#include<queue>
#include<unordered_map>
#include<algorithm>
using namespace std;
void printBit(int num){//int打印为二进制固定26位，观察环交换是否正确
int x=num;
string ans;
while(x!=0){
ans+=to_string(x&1);
x>>=1;
}
reverse(ans.begin(),ans.end());
int lessZero=26-ans.size();
while(lessZero--!=0)printf("0");
printf("%s-%d\n",ans.c_str(),num);
}
int moveUp(int s){
int up=s>>13,low=s&0x1fff;
up=((up&1)<<12)|(up>>1);
return up<<13|low;
}
int moveLow(int s){
int up=s>>13,low=s&0x1fff;
low=((low&1)<<12)|(low>>1);
return up<<13|low;
}
int exchange_fix(int s){
int up=s>>13,low=s&0x1fff;
int exup=up>>10,exlow=low>>10;
up=(exlow<<10)|(up&0x3ff);
low=(exup<<10)|(low&0x3ff);
return up<<13|low;
}
int mincode_one(int s){
int ms=s;
for(int i=0;i<13;i++){
int tmp=s&1;
s=(tmp<<12)|(s>>1);
if(ms>s)ms=s;
}
return ms;
}
int mincode_two(int s,unordered_map<int,int> &minnum){
int up=s>>13,low=s&0x1fff;
if(minnum.find(up)==minnum.end())minnum[up]=mincode_one(up);
if(minnum.find(low)==minnum.end())minnum[low]=mincode_one(low);
return minnum[up]<<13|minnum[low];
}
int main(){
int rightInt=0x3FFE000;
unordered_map<int,int> minNum_ans,numTominNum;
minNum_ans[rightInt]=0;
queue<int> q;
q.push(rightInt);
while(!q.empty()){
int currStatus=q.front();
q.pop();
int a=currStatus;
for(int i=0;i<13;i++){
a = moveUp(a);
int b=a;
for(int j=0;j<13;j++){
b=moveLow(b);
int nextStatus = exchange_fix(b);
nextStatus = mincode_two(nextStatus,numTominNum);
if(minNum_ans.find(nextStatus)==minNum_ans.end()){
minNum_ans[nextStatus]=minNum_ans[currStatus]+1;
q.push(nextStatus);
}
}
}
}
string s;
s.resize(26);
while(scanf("%s",&s[0])!=EOF){
int currentInt=0;
for(int i=0;i<26;i++){
if(s[i]=='g')currentInt=(currentInt<<1)+1;
else currentInt<<=1;
}
cout<<minNum_ans[mincode_two(currentInt,numTominNum)]<<endl;
}
}
v3.0将三个处理的函数改为之前字符串处理的方式处理int的上下环交换。AC了，但提交的运行时间比多50%左右，濒临超时。
#include<iostream>
#include<queue>
#include<unordered_map>
#include<algorithm>
using namespace std;
void printBit(int num){//int打印为二进制固定26位，观察环交换是否正确
int x=num;
string ans;
while(x!=0){
ans+=to_string(x&1);
x>>=1;
}
reverse(ans.begin(),ans.end());
int lessZero=26-ans.size();
while(lessZero--!=0)printf("0");
printf("%s-%d\n",ans.c_str(),num);
}
int exchange_NotFix(int s,int a,int b){
int up=s>>13,low=s&0x1fff,c,d;
for(int i=0;i<3;i++){
c=12-a%13,d=12-b%13;
int tmpup=(up&(1<<c))>>c,tmplow=(low&(1<<d))>>d;
up=up-(tmpup<<c)+(tmplow<<c);
low=low-(tmplow<<d)+(tmpup<<d);
a++;
b++;
}
return up<<13|low;
}
int mincode_one(int s){
int ms=s;
for(int i=0;i<13;i++){
int tmp=s&1;
s=(tmp<<12)|(s>>1);
if(ms>s)ms=s;
}
return ms;
}
int mincode_two(int s,unordered_map<int,int> &minnum){
int up=s>>13,low=s&0x1fff;
if(minnum.find(up)==minnum.end())minnum[up]=mincode_one(up);
if(minnum.find(low)==minnum.end())minnum[low]=mincode_one(low);
return minnum[up]<<13|minnum[low];
}
int main(){
int rightInt=0x3FFE000;
int cnt=0;
unordered_map<int,int> minNum_ans,numTominNum;
minNum_ans[rightInt]=0;
queue<int> q;
q.push(rightInt);
while(!q.empty()){
int currStatus=q.front();
q.pop();
for(int i=0;i<13;i++){
for(int j=0;j<13;j++){
int nextStatus = exchange_NotFix(currStatus,i,j);
nextStatus = mincode_two(nextStatus,numTominNum);
if(minNum_ans.find(nextStatus)==minNum_ans.end()){
minNum_ans[nextStatus]=minNum_ans[currStatus]+1;
q.push(nextStatus);
}
}
}
}
string s;
s.resize(26);
while(scanf("%s",&s[0])!=EOF){
int currentInt=0;
for(int i=0;i<26;i++){
if(s[i]=='g')currentInt=(currentInt<<1)+1;
else currentInt<<=1;
}
cout<<minNum_ans[mincode_two(currentInt,numTominNum)]<<endl;
}
}