2014
03-01

# WORM

Partychen discover a strange worm in ECNU.The worm is too laze so it spends most of his life in sleep,the only way to wake it up is turn the worm’s body into the same color. This worm’s body consist of N body sections, each body section could only be three kinds of colors: red (r), green (g), blue (b) . This worm’s body color could change with the following two rules:
1:two adjacent section with different colors can change into another at the same time, such as rg could be bb,bg could be rr etc.
2: only one change could happen in the worm’s body per second.
Illustration below shows a series change in two seconds:

Now Partychen want you to tell him how long it required to wake up the strange worm at least.

The first line of input contains one integer N( N<=200),specifying the number of test cases to follow.The following N lines each line contain a series characters denotes the color status of the worm’s body.’r’,’g’,’b’ represents “red”,”‘green”,”blue” respectively.there are no extra spaces or blanks in the characters and the total length of each line is at most 10.

The first line of input contains one integer N( N<=200),specifying the number of test cases to follow.The following N lines each line contain a series characters denotes the color status of the worm’s body.’r’,’g’,’b’ represents “red”,”‘green”,”blue” respectively.there are no extra spaces or blanks in the characters and the total length of each line is at most 10.

8
rbgrg
rbbgbbr
bgr
bgrbrgbr
bggrgbgrr
gbrggrbggr
rrrrr
bgbr

5
7
1
6
No solution!
8
0
4

//hdu 3088 WORM
/***********************************************
//题目网址：http://acm.hdu.edu.cn/showproblem.php?pid=3088
//题目大意：已知如下规则，求懒虫最早醒来时间：
//    <规则：
//    1、变化：懒虫的相邻部分[A,B]不一致时，才能够同时变色为C:
//     char change_colour(char a,char b)；
//    2、每秒只进行一次变化；当懒虫每个部分颜色一致时候，才会会醒来>
//具体思路：BFS
//出错笔记：额，超时：在查找该状态是否出现过的过程中消耗很多时间
//    解决方法：将worm的中间状态转换成数字，hash：一次判断就可以了
//     三进制可以将空间压缩，此外，3^10已经足够存储所有中间状态
//代码效率：Accepted 3088 62MS 292K 1989 B C++
// — BY Feng [2010/8/24]
***********************************************/
#include <stdio.h>
#include <memory>
#include <queue>
#include <iostream>
#define MAX_STEP 60000    //3^10:59049
using namespace std;

char worm[12];
int last[3];
bool is_used[MAX_STEP];
int len;
struct WORM
{
char worm[12];
int step;
};

char change_colour(char a,char b)
{    // r: 0        g:1        b:2
if(a+b == ’0′+’1′) return ’2′;
if(a+b == ’0′+’2′) return ’1′;
if(a+b == ’1′+’2′) return ’0′;
}
int my_atoi(char iworm[12])
{
int t=0;
for(int i=0;i<len;i++)
{
t=t*3+iworm[i]-’0′;
}
return t;
}
int BFS()
{
int i,step=0,flag;
int temp_mark;
char x,y;
WORM temp;
queue<WORM> que;
temp_mark = my_atoi(worm);
if(temp_mark==last[0]||temp_mark==last[1]||temp_mark==last[2])
return 0;
memset(is_used,false,sizeof(is_used));
strcpy(temp.worm,worm);
temp.step=0;
que.push(temp);
is_used[temp_mark]=true;
while(!que.empty())
{
temp=que.front();
temp.step++;
que.pop();
for(i=0;i<len-1;i++)
{
if(temp.worm[i]!=temp.worm[i+1])
{
x=temp.worm[i];
y=temp.worm[i+1];
temp.worm[i]=temp.worm[i+1]=change_colour(temp.worm[i],temp.worm[i+1]);
temp_mark=my_atoi(temp.worm);

if(temp_mark==last[0]||temp_mark==last[1]||temp_mark==last[2])
return temp.step;

flag=1;
if(is_used[temp_mark]==false)
{
is_used[temp_mark]=true;
que.push(temp);
}
temp.worm[i]=x;
temp.worm[i+1]=y;
}
}
}
return -1;
}
int main(void)
{
int n,count,i,j;
char last_worm[12];
scanf("%d",&n);
while(n–)
{
scanf("%s",worm);
len=strlen(worm);
for(i=0;i<len;i++)
{
if(worm[i]==’r') worm[i]=’0′;
else if(worm[i]==’g') worm[i] =’1′;
else if(worm[i]==’b') worm[i] =’2′;
}
for(i=0;i<3;i++)
{
for(j=0;j<len;j++)
last_worm[j]=i+’0′;
last_worm[len]=’\0′;
last[i]=my_atoi(last_worm);
}
count= BFS();
if(count!=-1)
printf("%d\n",count);
else
printf("No solution!\n");
}
}

1. 第一题是不是可以这样想，生了n孩子的家庭等价于n个家庭各生了一个1个孩子，这样最后男女的比例还是1:1