首页 > 代码库 > POJ 1027 The Same Game(模拟)

POJ 1027 The Same Game(模拟)

2024-07-17 20:34:04   215人阅读

题目链接

题意 ： 一个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:\n\n",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.\n",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.\n\n",sum,tot);125     }126     return 0;127 }
View Code

 


联系
我们