2014
02-24

# 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

1.b可以直接放入

2.r放入周围必须有b

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

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

#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;
}

1. 那个，大家，这个是demo，只有固定的几个姿势，一共只有四个单独的软件，要求并不高，我GT840跑标准的没问题（微卡），油瓶只发出了一个，我这里给出四个的，以便大家学习借鉴：链接: ***pan.baidu.com/s/1qWxGZak 密码: n9h8

2. 那个，大家，这个是demo，只有固定的几个姿势，一共只有四个单独的软件，要求并不高，我GT840跑标准的没问题（微卡），油瓶只发出了一个，我这里给出四个的，以便大家学习借鉴：链接: ***pan.baidu.com/s/1qWxGZak 密码: n9h8

3. 那个，大家，这个是demo，只有固定的几个姿势，一共只有四个单独的软件，要求并不高，我GT840跑标准的没问题（微卡），油瓶只发出了一个，我这里给出四个的，以便大家学习借鉴：链接: ***pan.baidu.com/s/1qWxGZak 密码: n9h8

4. 那个，大家，这个是demo，只有固定的几个姿势，一共只有四个单独的软件，要求并不高，我GT840跑标准的没问题（微卡），油瓶只发出了一个，我这里给出四个的，以便大家学习借鉴：链接: ***pan.baidu.com/s/1qWxGZak 密码: n9h8

5. 那个，大家，这个是demo，只有固定的几个姿势，一共只有四个单独的软件，要求并不高，我GT840跑标准的没问题（微卡），油瓶只发出了一个，我这里给出四个的，以便大家学习借鉴：链接: ***pan.baidu.com/s/1qWxGZak 密码: n9h8

6. 那个，大家，这个是demo，只有固定的几个姿势，一共只有四个单独的软件，要求并不高，我GT840跑标准的没问题（微卡），油瓶只发出了一个，我这里给出四个的，以便大家学习借鉴：链接: ***pan.baidu.com/s/1qWxGZak 密码: n9h8

7. 那个，大家，这个是demo，只有固定的几个姿势，一共只有四个单独的软件，要求并不高，我GT840跑标准的没问题（微卡），油瓶只发出了一个，我这里给出四个的，以便大家学习借鉴：链接: ***pan.baidu.com/s/1qWxGZak 密码: n9h8

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

9. 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.

10. 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;

11. 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

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