POJ 1027 The Same Game(模拟)

时间：2024-04-15 03:27:16

题目链接

题意 ： 一个10×15的格子，有三种颜色的球，颜色相同且在同一片内的球叫做cluster（具体解释就是，两个球颜色相同且一个球可以通过上下左右到达另一个球，则这两个球属于同一个cluster，同时cluster含有至少两个球），每次选择cluster中包含同色球最多的进行消除，每次消除完之后，上边的要往下移填满空的地方，一列上的球移动之前与之后相对位置不变，如果有空列，右边的列往左移动，每一列相对位置不变 。

思路 ： 模拟。。。。。。不停的递归。。。。。

 ////POJ 1027

 #include <iostream>

 #include <string>

 #include <cstdio>

 #include <cstring>

 using namespace std;

 int tmp,ans,tot,sum,k,xx,yy;

 //tmp：cluster中同色球的个数，ans:每次要消除的球的个数，tot：当前图中剩的总的有颜色的球，sum，分值，k:步数，xx，yy指的是要消除的cluster是从该点开始的

 bool v[][];

 string a[];

 char ch;

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

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

 void remov(int x,int y)//递归消除掉同色的

 {

     char c = a[x][y];

     a[x][y] = '';

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

     {

         int xx = x + dx[i];

         int yy = y + dy[i];

         if (xx >=  && yy >=  && xx <  && yy <  && a[xx][yy] == c)

             remov(xx,yy);

     }

 }

 void cluster(int x,int y)

 {

     tmp++;

     v[x][y] = ;

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

     {

         int xx = x + dx[k];

         int yy = y + dy[k];

         if (xx >=  && yy >=  && xx <  && yy <  && !v[xx][yy] && a[xx][yy]==a[x][y])

             cluster(xx,yy);

     }

 }

 int Find()

 {

     int maxx = ;

     memset(v,,sizeof(v));

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

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

             if (!v[i][j] && a[i][j]!='')

             {

                 tmp = ;

                 cluster(i,j);

                 if (tmp > maxx)

                 {

                     maxx = tmp;

                     ch = a[xx = i][yy = j];

                 }

             }

     return maxx;

 }

 void fresh()

 {

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

     {

         int cnt = ;

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

             if (a[i][j] == '') cnt++;

         for (int i =  ; i < -cnt ; i++)

             while (a[i][j]=='')//因为是倒着输入的，所以换不是往上换

             {

                 int c = i;

                 while (c != )

                 {

                     swap(a[c][j],a[c+][j]);

                     c++;

                 }

             }

     }

     int vis1[],tmpx = ;

     memset(vis1,,sizeof(vis1));

     for (int j =  ; j <  ; j++)//找空列

     {

         int cnt = ;

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

             if (a[i][j] == '') cnt++;

         if (cnt == )

         {

             vis1[j] = ;

             tmpx++;

         }

     }

     for (int j =  ; j < -tmpx ; j++)

         while (vis1[j] == )

         {

             int c = j;

             while (c != )

             {

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

                     swap(a[i][c],a[i][c+]);

                 swap(vis1[c],vis1[c+]);

                 c++;

             }

         }

 }

 int main()

 {

     int T ,casee = ;

     scanf("%d",&T);

     while(T--)

     {

         for (int i=; i>=; i--)

             cin >> a[i];

         printf("Game %d:\n\n",casee ++);

         tot = ;

         k = ;

         sum = ;

         while ()

         {

             ans = Find();

             if (ans <= ) break;

             printf("Move %d at (%d,%d): removed %d balls of color %c, got %d points.\n",

                    k++,xx+,yy+,ans,ch,(ans-)*(ans-));

             tot -= ans;

             sum += (ans-)*(ans-);

             remov(xx,yy);

             fresh();

         }

         if (tot == ) sum += ;

         printf("Final score: %d, with %d balls remaining.\n\n",sum,tot);

     }

     return ;

 }

相关文章