129
uva 704 - Colour Hash map+雙向bfs
這題從上周日開始想寫的，結果拖了一周……現在寫題效率越來越低了，要計時訓練了。
一道很複雜的隱式圖搜索……狀態數有24位，看到網上有人按11進製轉換，然後對Hash_MAX取模，個人認為這種做法不靠譜。於是把狀態變成string類型的，直接用map，對於map，24位的string效率還是非常高的。
搜索的時候雙向bfs，因為比較懶，所以把反向和正向寫一起了，其實逆向隻用做一次就可以了。
還有一點要注意的就是要輸出數字最小的一種變換序號，這個處理方法就是把一層都搜索完，看到網上有人的代碼完全沒考慮，最後居然還過了，隻能說數據水了……
輸出逆向bfs時注意是逆變換。
/*
author:jxy
lang:C/C++
university:China,Xidian University
**If you need to reprint,please indicate the source**
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <queue>
#include<map>
#define INF 1E9
using namespace std;
const int Aim[24]={0,3,4,3,0,5,6,5,0,1,2,1,0,7,8,7,0,9,10,9,0,1,2,1};
string aim;
struct node
{
int c,flag,i;//c表示走過路程，flag-1為正向，2為逆向，i為操作序號
string fa;//父狀態
};
string t;
string turn(string s,int num)//變換
{
string now;
switch(num)
{
case 1:now=s.substr(10,2)+s.substr(0,10)+s.substr(12,9);
now+=now.substr(9,3);return now;
case 3:now=s.substr(2,10)+s.substr(0,2)+s.substr(12,9);
now+=now.substr(9,3);return now;
case 4:now=s.substr(0,9)+s.substr(22,2)+s.substr(12,10);
now.insert(9,now.substr(18,3));return now;
case 2:now=s.substr(0,9)+s.substr(14,10)+s.substr(12,2);
now.insert(9,now.substr(18,3));return now;
default: return s;
}
}
string input()
{
int i,j;
string now="";
aim="";
for(i=0;i<24;i++)
{
scanf("%d",&j);
now.push_back(j);
aim.push_back(Aim[i]);
}
return now;
}
map<string,node> vis;
queue<string> q;
node next;
int out[20],no=0,nt,tt[20];
void output(string nn)//向前遞歸輸出
{
if(vis[nn].fa=="-1")return;
output(vis[nn].fa);
tt[nt++]=vis[nn].i;
}
void print(string now,string t,int i)
{
nt=0;
if(vis[now].flag==2)swap(now,t);//判斷前後遍曆節點
output(now);//向前遍曆
tt[nt++]=i;//中間
for(t;vis[t].fa!="-1";t=vis[t].fa)tt[nt++]=vis[t].i;//向後遍曆
if(nt<no||no==0){no=nt;memcpy(out,tt,sizeof(tt));}//比大小
else if(nt>no)return;
for(i=0;i<nt&&out[i]==tt[i];i++);
if(out[i]>tt[i]){memcpy(out,tt,sizeof(tt));}
}
bool solve(string s)//雙向bfs
{
if(s==aim){cout<<"PUZZLE ALREADY SOLVED"<<endl;return 1;}
vis.clear();
while(!q.empty())q.pop();
next.c=1;next.fa="-1";next.flag=1;next.i=0;vis[s]=next;
q.push(s);//正向起點
next.flag=2;vis[aim]=next;
q.push(aim);//逆向起點
bool flag=1;
string now;
int i,last;
while(!q.empty())
{
now=q.front();q.pop();
next.flag=vis[now].flag;
next.c=vis[now].c+1;
if(next.c>last&&!flag)break;//把這一層全遍曆完，以確定最小值
next.fa=now;
if(next.c>9){cout<<"NO SOLUTION WAS FOUND IN 16 STEPS"<<endl;return 1;}
for(i=1;i<=4;i++)
{
if(next.flag==1) t=turn(now,i);
else t=turn(now,(i+1)%4+1);
next.i=i;
if(vis[t].c!=0)
if(vis[t].flag==next.flag)continue;
else {flag=0;print(now,t,i);break;}
q.push(t);vis[t]=next;
}
last=next.c;
}
return 0;
}
int main()
{
int T;
scanf("%d",&T);
string org;
while(T--)
{
no=0;
if(solve(input()))continue;
for(int i=0;i<no;i++) printf("%d",out[i]);
puts("");
}
}
最後更新：2017-04-02 00:06:53