Problem 1006 - 转盘游戏
Time Limit: 1000MS Memory Limit: 65536KB Difficulty:
Total Submit: 87 Accepted: 42 Special Judge: No
Total Submit: 87 Accepted: 42 Special Judge: No
Description
wm最近喜欢上一种无聊的转盘解锁游戏，他每天都会为这游戏消磨上三个小时的时间。这游戏由三个正六边形拼成，拼成后一共有13个点，其中有4个黑点和9个白点，如下图。每一步可以顺时针或逆时针转动三个六边形的任意一个60度，转动时六边形的顶点也会相应转动，而这游戏的目的是把四个黑点都转到中间（图中最后一个状态）。这是一个很简单的游戏，想达到游戏目的并不难，但wm觉得这样没挑战性，他决定对于任意一个初始状态，用最少的步数去玩这个游戏。
Input
输入包含多组数据（500组），EOF结束。
每组数据都只有一行13个字符的01串，以从上到下，从左到右的点的顺序表示初始状态（这个由三个正六边形拼成图形最上面一排两个点编号为1 2，第二排三个点编号为3 4 5，依此类推，最后一个点编号为13。第一组样例为上图的初始状态），其中1表示黑点0表示白点。
每组数据都只有一行13个字符的01串，以从上到下，从左到右的点的顺序表示初始状态（这个由三个正六边形拼成图形最上面一排两个点编号为1 2，第二排三个点编号为3 4 5，依此类推，最后一个点编号为13。第一组样例为上图的初始状态），其中1表示黑点0表示白点。
Output
每组数据输出一行，解出游戏需要的最小步数。
Sample Input
0000000101011
1011000001000
1011000001000
Sample Output
3
2
2
Hint
Source
2010.04内部测试赛
#include<stdio.h>
#include<string.h>
#include<queue>
using namespace std;
struct node
{
int step;
int state[];
};
int shift[][]={{,,,,,},{,,,,,},{,,,,,}};
char str[];
bool f[];
int encode(node x)
{
int i,ans=;
for (i=;i<=;i++) ans=ans*+x.state[i];
return ans;
}
bool finish(node x)
{
if (x.state[]==) return false;
if (x.state[]==) return false;
if (x.state[]==) return false;
if (x.state[]==) return false;
return true;
}
int bfs()
{
queue<node> q;
while (!q.empty()) q.pop();
memset(f,false,sizeof(f));
node s,tmp;
int i,j,t;
for (i=;i<=;i++) s.state[i]=str[i]-;
s.step=;
q.push(s);
f[encode(s)]=true;
while (!q.empty())
{
s=q.front();
q.pop();
if (finish(s)) return s.step;
for (i=;i<;i++)
{
tmp=s;
for (j=;j<;j++) tmp.state[shift[i][(j+)%]]=s.state[shift[i][j]];
tmp.step++;
t=encode(tmp);
if (!f[t])
{
f[t]=true;
q.push(tmp);
}
//shift[i][(j+1)%6]<-shift[i][j]
tmp=s;
for (j=;j<;j++) tmp.state[shift[i][(j+)%]]=s.state[shift[i][j]];
tmp.step++;
t=encode(tmp);
if (!f[t])
{
f[t]=true;
q.push(tmp);
}
//shift[i][j]->shift[i][(j+5)%6]
}
}
return -;
}
int main()
{
while (scanf("%s",&str[])!=EOF)
{
scanf("%s",&str[]);
int ans=bfs();
printf("%d\n",ans);
}
return ;
}