POJ 1027 The Same Game(模拟)

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

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

  1 ////POJ 1027
  2 #include <iostream>
  3 #include <string>
  4 #include <cstdio>
  5 #include <cstring>
  6 using namespace std;
  7 int tmp,ans,tot,sum,k,xx,yy;
  8 //tmp：cluster中同色球的个数，ans:每次要消除的球的个数，tot：当前图中剩的总的有颜色的球，sum，分值，k:步数，xx，yy指的是要消除的cluster是从该点开始的
  9 bool v[11][16];
 10 string a[11];
 11 char ch;
 12 int dx[4] = {0,1,0,-1};
 13 int dy[4] = {1,0,-1,0};
 14 void remov(int x,int y)//递归消除掉同色的
 15 {
 16     char c = a[x][y];
 17     a[x][y] = '0';
 18     for (int i = 0 ; i < 4 ; i++)
 19     {
 20         int xx = x + dx[i];
 21         int yy = y + dy[i];
 22         if (xx >= 0 && yy >= 0 && xx < 10 && yy < 15 && a[xx][yy] == c)
 23             remov(xx,yy);
 24     }
 25 }
 26 void cluster(int x,int y)
 27 {
 28     tmp++;
 29     v[x][y] = 1;
 30     for (int k = 0 ; k < 4 ; k++)
 31     {
 32         int xx = x + dx[k];
 33         int yy = y + dy[k];
 34         if (xx >= 0 && yy >= 0 && xx < 10 && yy < 15 && !v[xx][yy] && a[xx][yy]==a[x][y])
 35             cluster(xx,yy);
 36     }
 37 }
 38 int Find()
 39 {
 40     int maxx = 0;
 41     memset(v,0,sizeof(v));
 42     for (int j = 0; j < 15; j++)
 43         for (int i = 0; i < 10; i++)
 44             if (!v[i][j] && a[i][j]!='0')
 45             {
 46                 tmp = 0;
 47                 cluster(i,j);
 48                 if (tmp > maxx)
 49                 {
 50                     maxx = tmp;
 51                     ch = a[xx = i][yy = j];
 52                 }
 53             }
 54     return maxx;
 55 }
 56 void fresh()
 57 {
 58     for (int j = 0 ; j < 15 ; j++)
 59     {
 60         int cnt = 0;
 61         for (int i = 0 ; i < 10 ; i++)
 62             if (a[i][j] == '0') cnt++;
 63         for (int i = 0 ; i < 10-cnt ; i++)
 64             while (a[i][j]=='0')//因为是倒着输入的，所以换不是往上换
 65             {
 66                 int c = i;
 67                 while (c != 9)
 68                 {
 69                     swap(a[c][j],a[c+1][j]);
 70                     c++;
 71                 }
 72             }
 73     }
 74     int vis1[16],tmpx = 0;
 75     memset(vis1,0,sizeof(vis1));
 76     for (int j = 0 ; j < 15 ; j++)//找空列
 77     {
 78         int cnt = 0;
 79         for (int i = 0 ; i < 10; i++)
 80             if (a[i][j] == '0') cnt++;
 81         if (cnt == 10)
 82         {
 83             vis1[j] = 1;
 84             tmpx++;
 85         }
 86     }
 87     for (int j = 0 ; j < 15-tmpx ; j++)
 88         while (vis1[j] == 1)
 89         {
 90             int c = j;
 91             while (c != 14)
 92             {
 93                 for (int i = 0 ; i < 10; i++)
 94                     swap(a[i][c],a[i][c+1]);
 95                 swap(vis1[c],vis1[c+1]);
 96                 c++;
 97             }
 98         }
 99 }
100 int main()
101 {
102     int T ,casee = 1;
103     scanf("%d",&T);
104     while(T--)
105     {
106         for (int i=9; i>=0; i--)
107             cin >> a[i];
108         printf("Game %d:

",casee ++);
109         tot = 150;
110         k = 1;
111         sum = 0;
112         while (1)
113         {
114             ans = Find();
115             if (ans <= 1) break;
116             printf("Move %d at (%d,%d): removed %d balls of color %c, got %d points.
",
117                    k++,xx+1,yy+1,ans,ch,(ans-2)*(ans-2));
118             tot -= ans;
119             sum += (ans-2)*(ans-2);
120             remov(xx,yy);
121             fresh();
122         }
123         if (tot == 0) sum += 1000;
124         printf("Final score: %d, with %d balls remaining.

",sum,tot);
125     }
126     return 0;
127 }

View Code