UVALive 4025 Color Squares(BFS)

按题意要求放带有颜色的块，求达到w分的最少步数。
//yy：哇，看别人存下整个棋盘的状态来做，我什么都不想说了，不知道下午自己写了些什么东西，训练结束补的、、
 #include <cstdio>

 #include <cstring>

 #include <algorithm>

 #include <queue>

 #define CLR(a, b) memset((a),(b),sizeof((a)))

 using namespace std;

 const int inf = 0x3f3f3f3f;

 int dp[][][][];

 bool vis[][][][][][][][][];//整个棋盘

 int dx[] = {,,-,};

 int dy[] = {,,,-};

 struct node {

     int w;

     int c[], g[][];

     node(int _w = ):w(_w){CLR(c, ); CLR(g, );}

 }t,p;

 bool jud(node p) {

     if(!vis[p.g[][]][p.g[][]][p.g[][]][p.g[][]][p.g[][]][p.g[][]][p.g[][]][p.g[][]][p.g[][]])

         return true, vis[p.g[][]][p.g[][]][p.g[][]][p.g[][]][p.g[][]][p.g[][]][p.g[][]][p.g[][]][p.g[][]] = ;

     return false;

 }

 void bfs() {

     int i, j, k, o, x, y;

     queue<node> q;

     q.push(node());

     vis[][][][][][][][][] = ;

     while(!q.empty()) {

         t = q.front(); q.pop();

         dp[t.c[]][t.c[]][t.c[]][t.c[]]=min(t.w,dp[t.c[]][t.c[]][t.c[]][t.c[]]);

         for(i = ; i < ; ++i) {

             for(j = ; j < ; ++j) {

                 int b=,r=,g=;

                 for(k = ; k < ; ++k) {

                     x = i + dx[k];

                     y = j + dy[k];

                     if(x >= && y >=  && x <  && y < ) {

                         if(t.g[x][y]==) b++;

                         else if(t.g[x][y]==) r++;

                         else if(t.g[x][y]==) g++;

                     }

                 }

                 int cc = t.g[i][j];

                 p.w = t.w + ;

                 if(cc != ) {//蓝

                     for(k = ; k < ; ++k) p.c[k] = t.c[k];

                     for(k = ; k < ; ++k)for(o = ; o < ; ++o) p.g[k][o] = t.g[k][o];

                     p.c[cc] = t.c[cc] - ;

                     p.c[] = t.c[] + ;

                     p.g[i][j] = ;

                     if(jud(p)) q.push(p);

                 }

                 if(cc !=  && b) {//红

                     for(k = ; k < ; ++k) p.c[k] = t.c[k];

                     for(k = ; k < ; ++k)for(o = ; o < ; ++o) p.g[k][o] = t.g[k][o];

                     p.c[cc] = t.c[cc] - ;

                     p.c[] = t.c[] + ;

                     p.g[i][j] = ;

                     if(jud(p)) q.push(p);

                 }

                 if(cc !=  && b && r) {//绿

                     for(k = ; k < ; ++k) p.c[k] = t.c[k];

                     for(k = ; k < ; ++k)for(o = ; o < ; ++o) p.g[k][o] = t.g[k][o];

                     p.c[cc] = t.c[cc] - ;

                     p.c[] = t.c[] + ;

                     p.g[i][j] = ;

                     if(jud(p)) q.push(p);

                 }

                 if(cc !=  && b && r && g) {//黄

                     for(k = ; k < ; ++k) p.c[k] = t.c[k];

                     for(k = ; k < ; ++k)for(o = ; o < ; ++o) p.g[k][o] = t.g[k][o];

                     p.c[cc] = t.c[cc] - ;

                     p.c[] = t.c[] + ;

                     p.g[i][j] = ;

                     if(jud(p)) q.push(p);

                 }

             }

         }

     }

 }

 int main() {

     CLR(dp, inf);CLR(vis,false);bfs();

     int ka = , b, r, g, y, w, i, j, k, o;

     while(~scanf("%d", &b), b) {

         scanf("%d%d%d%d", &r, &g, &y, &w);

         printf("Case %d: ", ka++);

         int ans = inf;

         for(i=;i<;++i)for(j=;j<;++j)for(k=;k<;++k)for(o=;o<;++o)

         if(b*i+r*j+g*k+y*o >= w) ans = min(ans, dp[i][j][k][o]);

         if(ans < inf) printf("%d\n" ,ans);

         else puts("Impossible");

     }

     return ;

 }