The Same Game(模拟)

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
char map[15][20];
int ansr,ansc,ansb,q[170][2],head,tail;
char anscol;
bool vis[15][20];
const int move[4][2] = {{-1,0},{1,0},{0,1},{0,-1}};
int area(int x,int y)
{
   head = tail = 0;
   q[++tail][0] = x; q[tail][1] = y;
   char col = map[x][y];
   int size = 0,i;
   vis[x][y] = 1;
   while (head < tail)
    {
       int nowx = q[++head][0],nowy = q[head][1];
       size ++;
       for (i = 0;i < 4;i ++)
           if (nowx + move[i][0] >= 0 && nowx + move[i][0] < 10
               && nowy + move[i][1] >= 0 && nowy + move[i][1] < 15
               && map[nowx + move[i][0]][nowy + move[i][1]] == col
               && !vis[nowx + move[i][0]][nowy + move[i][1]])
               {
               q[++tail][0] = nowx + move[i][0];
               q[tail][1] = nowy + move[i][1];
               vis[nowx + move[i][0]][nowy + move[i][1]] = 1;
               }
   }
   return size;
}
void del()
{
   head = tail = 0;
   q[++tail][0] = ansr; q[tail][1] = ansc;
   anscol = map[ansr][ansc];
   map[ansr][ansc] = 0;
   while (head < tail)
    {
       int nowx = q[++head][0],nowy = q[head][1];
       map[nowx][nowy] = 0;
       for (int i = 0;i < 4;i ++)
           if (nowx + move[i][0] >= 0 && nowx + move[i][0] < 10
               && nowy + move[i][1] >= 0 && nowy + move[i][1] < 15
               && map[nowx + move[i][0]][nowy + move[i][1]] == anscol)
               {
               q[++tail][0] = nowx + move[i][0];
               q[tail][1] = nowy + move[i][1];
               map[nowx + move[i][0]][nowy + move[i][1]] = 0;
               }
   }
   return;
}
void calc()
{
   int i,j;
   memset(vis,0,sizeof vis);
   for (j = 0;j < 15;j ++)
       for (i = 0;i < 10;i ++)
       {
           int size = 0;
           if (!vis[i][j] && map[i][j]) size = area(i,j);
           if (size > ansb) ansb = size,ansr = i,ansc = j;
       }
   return;
}
void refresh()
{
   bool empty[20] = {false};
   for (int j = 0;j < 15; j ++)
    {
       int flag = false,pi = -1;
       for (int i = 0;i < 10;i ++)
       {
           if (map[i][j])
           {
               flag = true;
               if (pi != -1)
               {
                   map[pi][j] = map[i][j];
                   map[i][j] = 0;
                   i = pi;
                   pi = -1;
               }
           }
           else
           {
               pi = i;
               while (i + 1 < 10 && !map[i + 1][j]) i ++;
           }
       }
       if (!flag) empty[j] = true;
   }
   int k = -1;
   for (int j = 0;j < 15;j ++)
   {
       if (!empty[j])
       {
           if (k != -1)
           {
               for (int i = 0;i < 10;i ++)
               {
                   map[i][k] = map[i][j];
                   map[i][j] = 0;
               }
               empty[j] = true;
               j = k;
               k = -1;
           }
       }
       else
       {
           k = j;
           while (j + 1 < 15 && empty[j + 1]) j ++;
       }
   }
   return ;
}
int main()
{
   int T,times,i;
   scanf("%d",&T);
   for (times = 1;times <= T;times ++)
    {
       memset(map,0,sizeof map);
       for (i = 9;i >= 0;i --) scanf("%s",map[i]);
       printf("Game %d:\n\n",times);
       int step = 0,rem = 150,score = 0;
       for (;;)
       {
           ++step;
           ansr = 0,ansc = 0,ansb = -1;
           calc();
           if (ansb == 0 || ansb == 1) break;
           del();
           refresh();
           int s = (ansb - 2) * (ansb - 2);
           printf("Move %d at (%d,%d): ",step,ansr + 1,ansc + 1);
           printf("removed %d balls of color %c, got %d points.\n",ansb,anscol,s);
           rem -= ansb;
           score += s;
       }
       if (rem == 0) score += 1000;
       printf("Final score: %d, with %d balls remaining.\n\n",score,rem);
   }
   return 0;
}

The Same Game(模拟)

原文：http://www.cnblogs.com/You-Change/p/3530958.html