首页 > 搜索 > BFS搜索 > HDU 3088-WORM-BFS-[解题报告]HOJ
2014
03-01

HDU 3088-WORM-BFS-[解题报告]HOJ

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:
Aqua Splash

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");
}
}

参考:http://hi.baidu.com/for_wind_/item/1c41aa2a7d2a59c5dcf69aeb


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

  2. Hello Web Admin, I noticed that your On-Page SEO is is missing a few factors, for one you do not use all three H tags in your post, also I notice that you are not using bold or italics properly in your SEO optimization. On-Page SEO means more now than ever since the new Google update: Panda. No longer are backlinks and simply pinging or sending out a RSS feed the key to getting Google PageRank or Alexa Rankings, You now NEED On-Page SEO. So what is good On-Page SEO?First your keyword must appear in the title.Then it must appear in the URL.You have to optimize your keyword and make sure that it has a nice keyword density of 3-5% in your article with relevant LSI (Latent Semantic Indexing). Then you should spread all H1,H2,H3 tags in your article.Your Keyword should appear in your first paragraph and in the last sentence of the page. You should have relevant usage of Bold and italics of your keyword.There should be one internal link to a page on your blog and you should have one image with an alt tag that has your keyword….wait there's even more Now what if i told you there was a simple WordPress plugin that does all the On-Page SEO, and automatically for you? That's right AUTOMATICALLY, just watch this 4minute video for more information at.