題目描述：

Problem Description
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.

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

Output
For each test case, print the case number and the minimum number of steps. If it is impossible, output “Impossible”.

Sample Input

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

Sample Output

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

Source
2007 Asia Regional Beijing

題目分析：

一個(gè)3*3的正方形方格中，可以填入B R G Y 四種顏色。（初始網(wǎng)格無(wú)色）
其中，B色填涂無(wú)需別的約束條件；
R色填涂需要其方格上下左右四個(gè)方向中至少有一個(gè)方格顏色為B；
G色填涂需要其方格上下左右四個(gè)方向中至少有一個(gè)方格顏色為B，至少有一個(gè)方格顏色為R；
Y色填涂需要其方格上下左右四個(gè)方向中分別至少有一個(gè)B，一個(gè)R，一個(gè)G。
方格在每種不同的顏色都有其特殊的分?jǐn)?shù)，其中保證Vy>=Vg>=Vr>=Vb。
你的最終得分為每個(gè)方格中的得分之和。
你可以將一個(gè)已經(jīng)填了顏色的方格重新填色，新的顏色會(huì)覆蓋原顏色。
給一個(gè)w，求你在最少的步數(shù)能夠達(dá)到或大于這個(gè)分?jǐn)?shù)。

其實(shí)BFS的搜索思路還是很清晰的，就是問(wèn)題是如何存儲(chǔ)復(fù)雜的狀態(tài)，由于這個(gè)網(wǎng)格是3*3的，也就是說(shuō)只有9個(gè)方格，所以我們可以用9維數(shù)組來(lái)存儲(chǔ)狀態(tài)是否被訪問(wèn)（每一維記錄這個(gè)方格的狀態(tài)），用4維數(shù)組記錄到達(dá)這四種顏色狀態(tài)的最短步數(shù)（因?yàn)闄?quán)和之和方格上的顏色和其個(gè)數(shù)決定，和其位置無(wú)關(guān)），然后就是BFS搜索填涂四種顏色的情況。
其實(shí)這道題如果網(wǎng)格更大，就不能用數(shù)組存儲(chǔ)狀態(tài)了，因?yàn)闀?huì)MLE（而且寫起來(lái)也要爆炸），就是一道BFS+狀壓的題，然而這題每個(gè)方格狀態(tài)有5個(gè)，也就是壓縮成5進(jìn)制了。（和普通的二進(jìn)制狀壓不同了）
不過(guò)這些都是后話。
這題的算法就是這樣。

代碼如下：

#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <cstdlib> #include <queue>const int INF=0x3f3f3f3f; using namespace std;int vis[5][5][5][5][5][5][5][5][5]; int dir[4][2]= {-1,0,1,0,0,-1,0,1}; int steps[10][10][10][10]; struct sa {int mp[3][3];int step;int num[5]; };int b,r,g,y,w; int cas;void init() {memset(vis,0,sizeof(vis));memset(steps,INF,sizeof(steps)); }void BFS() {queue<sa>q;sa u;u.step=0;memset(u.mp,0,sizeof(u.mp));memset(u.num,0,sizeof(u.num));q.push(u);vis[0][0][0][0][0][0][0][0][0]=1;while(!q.empty()){sa u=q.front();q.pop();steps[u.num[1]][u.num[2]][u.num[3]][u.num[4]]=min(u.step,steps[u.num[1]][u.num[2]][u.num[3]][u.num[4]]);for(int i=0; i<3; i++)for(int j=0; j<3; j++){int num1=0,num2=0,num3=0;int pre=u.mp[i][j];//print Bif (u.mp[i][j]!=1){u.step++;u.num[1]++;u.num[pre]--;u.mp[i][j]=1;if (!vis[u.mp[0][0]][u.mp[0][1]][u.mp[0][2]][u.mp[1][0]][u.mp[1][1]][u.mp[1][2]][u.mp[2][0]][u.mp[2][1]][u.mp[2][2]]){vis[u.mp[0][0]][u.mp[0][1]][u.mp[0][2]][u.mp[1][0]][u.mp[1][1]][u.mp[1][2]][u.mp[2][0]][u.mp[2][1]][u.mp[2][2]]=1;q.push(u);}u.mp[i][j]=pre;u.num[pre]++;u.num[1]--;u.step--;}//print Rfor(int k=0; k<4; k++){int nx=i+dir[k][0];int ny=j+dir[k][1];if (nx>=0 && ny>=0 && nx<3 && ny<3){if (u.mp[nx][ny]==1) num1++;}}if (num1 && u.mp[i][j]!=2){u.step++;u.num[2]++;u.num[pre]--;u.mp[i][j]=2;if (!vis[u.mp[0][0]][u.mp[0][1]][u.mp[0][2]][u.mp[1][0]][u.mp[1][1]][u.mp[1][2]][u.mp[2][0]][u.mp[2][1]][u.mp[2][2]]){vis[u.mp[0][0]][u.mp[0][1]][u.mp[0][2]][u.mp[1][0]][u.mp[1][1]][u.mp[1][2]][u.mp[2][0]][u.mp[2][1]][u.mp[2][2]]=1;q.push(u);}u.mp[i][j]=pre;u.num[pre]++;u.num[2]--;u.step--;}//print Gnum1=0,num2=0,num3=0;for(int k=0; k<4; k++){int nx=i+dir[k][0];int ny=j+dir[k][1];if (nx>=0 && ny>=0 && nx<3 && ny<3){if (u.mp[nx][ny]==1) num1++;if (u.mp[nx][ny]==2) num2++;}}if (num1 && num2 && u.mp[i][j]!=3){u.step++;u.num[3]++;u.num[pre]--;u.mp[i][j]=3;if (!vis[u.mp[0][0]][u.mp[0][1]][u.mp[0][2]][u.mp[1][0]][u.mp[1][1]][u.mp[1][2]][u.mp[2][0]][u.mp[2][1]][u.mp[2][2]]){vis[u.mp[0][0]][u.mp[0][1]][u.mp[0][2]][u.mp[1][0]][u.mp[1][1]][u.mp[1][2]][u.mp[2][0]][u.mp[2][1]][u.mp[2][2]]=1;q.push(u);}u.mp[i][j]=pre;u.num[pre]++;u.num[3]--;u.step--;}//print Ynum1=0,num2=0,num3=0;for(int k=0; k<4; k++){int nx=i+dir[k][0];int ny=j+dir[k][1];if (nx>=0 && ny>=0 && nx<3 && ny<3){if (u.mp[nx][ny]==1) num1++;if (u.mp[nx][ny]==2) num2++;if (u.mp[nx][ny]==3) num3++;}}if (num1 && num2 && num3 && u.mp[i][j]!=4){u.step++;u.num[4]++;u.num[pre]--;u.mp[i][j]=4;if (!vis[u.mp[0][0]][u.mp[0][1]][u.mp[0][2]][u.mp[1][0]][u.mp[1][1]][u.mp[1][2]][u.mp[2][0]][u.mp[2][1]][u.mp[2][2]]){vis[u.mp[0][0]][u.mp[0][1]][u.mp[0][2]][u.mp[1][0]][u.mp[1][1]][u.mp[1][2]][u.mp[2][0]][u.mp[2][1]][u.mp[2][2]]=1;q.push(u);}u.mp[i][j]=pre;u.num[pre]++;u.num[4]--;u.step--;}}} }int main() {cas=0;init();BFS();while(scanf("%d",&b)!=-1 && (b!=0)){scanf("%d%d%d%d",&r,&g,&y,&w);printf("Case %d: ",++cas);int ans=INF;for(int i=0; i<=9; i++)for(int j=0; j<=9; j++)for(int k=0; k<=9; k++)for(int l=0; l<=9; l++)if (i*b+j*r+k*g+l*y>=w)ans=min(ans,steps[i][j][k][l]);if (ans==INF) printf("Impossible\n");else printf("%d\n", ans);}return 0; }

總結(jié)

以上是生活随笔為你收集整理的HDU 2977 Color Squares BFS的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。