首页 > 搜索 > BFS搜索 > HDU 2977-Color Squares-BFS-[解题报告]HOJ
2014
02-24

HDU 2977-Color Squares-BFS-[解题报告]HOJ

Color Squares

问题描述 :

You have a 3 * 3 board of color squares. Each square is either empty or has a block in it. Initially, all the squares are empty. There are four kinds of blocks: blue (B), red (R), green (G) and yellow (Y). Each of these block scores wb, wr, wg and wy , respectively (blocks of the same color always have the same score). We assume that wb<=wr<=wg<=wy .


In each step, you can place a new block in a square. If that square already has a block in it, take it out first (taking it out does not count as a step). You can do this as many times as you like (you’re given enough blocks for each color), as long as you follow these rules:

Rule 1: You can always place a blue block.
Rule 2: You can place a red block if and only if it’s surrounded by at least one blue block.
Rule 3: You can place a green block if and only if it’s surrounded by at least one blue and one red block.
Rule 4: You can place a yellow block if and only if it’s surrounded by at least one blue, one red and one green block

Every square is surrounded by squares that share one edge with it, so each of four corner squares is surrounded by exactly two squares, each of four squares on the edge (but not at corners) is surrounded by exactly three squares, and the center square is surrounded by exactly four squares.

Write a program to find the minimal number of steps needed to get a score of at least w . The total score is the sum of individual scores of each block on the current board, regardless of what blocks you’ve thrown away.

输入:

The input contains several test cases. Each case contains five positive integer, wb, wr, wg, wy, w (1<=wb<=wr<=wg<=wy≤100, 0<=w<=1000) in a single line. The last test case is followed by a single zero, which should not be processed.

输出:

The input contains several test cases. Each case contains five positive integer, wb, wr, wg, wy, w (1<=wb<=wr<=wg<=wy≤100, 0<=w<=1000) in a single line. The last test case is followed by a single zero, which should not be processed.

样例输入:

1 1 1 1 3 
1 2 4 8 21 
1 1 1 100 500 
7 20 53 94 395
0

样例输出:

Case 1: 3 
Case 2: 7 
Case 3: Impossible 
Case 4: 11

题目大意:

一个3*3的网格,你可以放入b,r,g,y,并且放入时分别得到wb,wr,wg,wy的权值。但放入时有如下限制:

1.b可以直接放入

2.r放入周围必须有b

3.g放入周围必须有b,r

4.y放入周围必须有b,r,g

最后,给你一个w,问你至少用几步可以使得总权值>=w。(多组case)

题解:

第一开始超时了,原因在于我没有预处理。其实只BFS一次就好。搜索时用step[i][j][k][z]记录棋盘得到i个b,j个r,k个g,z个y的最小步数。

以后对于每组case,直接从step数组里找到i*w[1]+j*w[2]+k*w[3]+z*w[4]>=w,且step[i][j][k][z]最小的即可,这样每次查找时的复杂度为O(10^4),可以很快通过所有数据。

这个题目我写的代码好长,不过还好一次修改就对了

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
struct que
{
    int a[4][4];
    int step;
    int b[5];
};
queue<que> q;
bool v[5][5][5][5][5][5][5][5][5];
int step[10][10][10][10];
const int dx[5]={0,1,0,-1,0},dy[5]={0,0,1,0,-1};
que t;
int maxw,w[5],sec,sum=0;
int work()
{
    int s1,s2,s3,x,y,last;
    while(!q.empty())
    {
        t=q.front();q.pop();
        if(t.step<step[t.b[1]][t.b[2]][t.b[3]][t.b[4]])
        step[t.b[1]][t.b[2]][t.b[3]][t.b[4]]=t.step;
        for(int i=1;i<=3;i++)
         for(int j=1;j<=3;j++)
        {
            sum++;
            last=t.a[i][j];
            //debug
            //yell
            s1=0,s2=0,s3=0;
             for(int k=1;k<=4;k++)
            {
                x=i+dx[k];y=j+dy[k];
                if(x>=1&&y>=1&&x<=3&&y<=3&&t.a[x][y]==1)s1++;
                if(x>=1&&y>=1&&x<=3&&y<=3&&t.a[x][y]==2)s2++;
                if(x>=1&&y>=1&&x<=3&&y<=3&&t.a[x][y]==3)s3++;
            }
              if(s1>0&&s2>0&&s3>0&&t.a[i][j]!=4)
            {
                t.a[i][j]=4;t.b[last]--;t.b[4]++;
                t.step++;
                   if(!v[t.a[1][1]][t.a[1][2]][t.a[1][3]][t.a[2][1]][t.a[2][2]][t.a[2][3]][t.a[3][1]][t.a[3][2]][t.a[3][3]])
                {
                    v[t.a[1][1]][t.a[1][2]][t.a[1][3]][t.a[2][1]][t.a[2][2]][t.a[2][3]][t.a[3][1]][t.a[3][2]][t.a[3][3]]=true;
                   //debug
                    q.push(t);
                }
                t.a[i][j]=last;
                t.b[last]++;t.b[4]--;
                t.step--;
            }
            //green
            s1=0,s2=0;
             for(int k=1;k<=4;k++)
            {
                x=i+dx[k];y=j+dy[k];
                if(x>=1&&y>=1&&x<=3&&y<=3&&t.a[x][y]==1)s1++;
                if(x>=1&&y>=1&&x<=3&&y<=3&&t.a[x][y]==2)s2++;
            }
              if(s1>0&&s2>0&&t.a[i][j]!=3)
            {
                t.a[i][j]=3;t.b[last]--;t.b[3]++;
                t.step++;
                    if(!v[t.a[1][1]][t.a[1][2]][t.a[1][3]][t.a[2][1]][t.a[2][2]][t.a[2][3]][t.a[3][1]][t.a[3][2]][t.a[3][3]])
                {
                    v[t.a[1][1]][t.a[1][2]][t.a[1][3]][t.a[2][1]][t.a[2][2]][t.a[2][3]][t.a[3][1]][t.a[3][2]][t.a[3][3]]=true;
                    q.push(t);
                }
                t.a[i][j]=last;
                t.b[last]++;t.b[3]--;
                t.step--;
            }
              //red
            s1=0;
            for(int k=1;k<=4;k++)
            {
                x=i+dx[k];y=j+dy[k];
                if(x>=1&&y>=1&&x<=3&&y<=3&&t.a[x][y]==1)s1++;
            }
             if(s1>0&&t.a[i][j]!=2)
            {
                t.a[i][j]=2;
                t.step++;t.b[last]--;t.b[2]++;
                  if(!v[t.a[1][1]][t.a[1][2]][t.a[1][3]][t.a[2][1]][t.a[2][2]][t.a[2][3]][t.a[3][1]][t.a[3][2]][t.a[3][3]])
                {
                    v[t.a[1][1]][t.a[1][2]][t.a[1][3]][t.a[2][1]][t.a[2][2]][t.a[2][3]][t.a[3][1]][t.a[3][2]][t.a[3][3]]=true;
                    q.push(t);
                }
                t.a[i][j]=last;
                t.b[last]++;t.b[2]--;
                t.step--;
            }
              //blue
            if(t.a[i][j]!=1)
            {
                t.step++;
                t.a[i][j]=1;t.b[last]--;t.b[1]++;
                 if(!v[t.a[1][1]][t.a[1][2]][t.a[1][3]][t.a[2][1]][t.a[2][2]][t.a[2][3]][t.a[3][1]][t.a[3][2]][t.a[3][3]])
                {
                    v[t.a[1][1]][t.a[1][2]][t.a[1][3]][t.a[2][1]][t.a[2][2]][t.a[2][3]][t.a[3][1]][t.a[3][2]][t.a[3][3]]=true;
                    q.push(t);
                }
                t.a[i][j]=last;
                t.b[last]++;t.b[1]--;
                t.step--;
            }
        }
    }
    return -1;
}
int main()
{
    for(int i=0;i<=9;i++)
     for(int j=0;j<=9;j++)
      for(int k=0;k<=9;k++)
       for(int z=0;z<=9;z++)
       step[i][j][k][z]=1<<28;
    w[1]=1;w[2]=2;w[3]=3;w[4]=4;maxw=1<<28;
    for(int i=1;i<=3;i++)
    for(int j=1;j<=3;j++)
    t.a[i][j]=0;
    t.step=0;
    t.b[1]=t.b[2]=t.b[3]=t.b[4]=0;
    memset(v,false,sizeof(v));
    v[0][0][0][0][0][0][0][0][0]=true;
    q.push(t);
    int ans=work();

    sec=0;w[0]=0;
    while(scanf("%d",&w[1]),w[1])
    {
        sec++;
        scanf("%d%d%d%d",&w[2],&w[3],&w[4],&maxw);
        ans=1<<28;
        for(int i=0;i<=9;i++)
         for(int j=0;j<=9;j++)
          for(int k=0;k<=9;k++)
           for(int z=0;z<=9;z++)
           if(i*w[1]+j*w[2]+k*w[3]+z*w[4]>=maxw && step[i][j][k][z]<ans)
           ans=step[i][j][k][z];
        printf("Case %d: ",sec);
        if(ans==1<<28)
        printf("Impossible\n");
        else
        printf("%d\n",ans);
    }
    return 0;
}

解题参考:http://blog.csdn.net/hyogahyoga/article/details/7855571


,
  1. 约瑟夫也用说这么长……很成熟的一个问题了,分治的方法解起来o(n)就可以了,有兴趣可以看看具体数学的第一章,关于约瑟夫问题推导出了一系列的结论,很漂亮

  2. simple, however efficient. A lot of instances it is difficult to get that a??perfect balancea?? among usability and appearance. I must say that youa??ve done a exceptional task with this. Also, the blog masses quite fast for me on Web explore.

  3. int half(int *array,int len,int key)
    {
    int l=0,r=len;
    while(l<r)
    {
    int m=(l+r)>>1;
    if(key>array )l=m+1;
    else if(key<array )r=m;
    else return m;
    }
    return -1;
    }
    这种就能避免一些Bug
    l,m,r
    左边是l,m;右边就是m+1,r;

  4. Thanks for using the time to examine this, I truly feel strongly about it and enjoy finding out far more on this subject matter. If achievable, as you achieve knowledge

  5. 很高兴你会喜欢这个网站。目前还没有一个开发团队,网站是我一个人在维护,都是用的开源系统,也没有太多需要开发的部分,主要是内容整理。非常感谢你的关注。