# include <iostream>
# include <queue>
using namespace std;
struct point
{
     int lh;
     int ll;
     char col;
     int num;

     void detect(int h,int l,char col,char map[11][16])
     {
          if(h<1||h>10||l<1||l>15) return;
          else if(map[h][l]!=col) return;
          else
          {
              this->col=col;
              map[h][l]=0;
              num++;
              if(l<ll||(l==ll&&h<lh))
              {
                lh=h;
                ll=l;
              }
              detect(h+1,l,col,map);
              detect(h-1,l,col,map);
              detect(h,l+1,col,map);
              detect(h,l-1,col,map);
          }
     }
};
class game
{
 public:
      point list[151];
      point res[151];
      int count;
      int res_c;
      char map[11][16];
      game(char temp[11][16])
      {
       count=res_c=0;
       for(int i=10;i>=1;i--)
         for(int j=1;j<=15;j++)
          map[10-i+1][j]=temp[i][j-1];
       buildlist();
      }
      void printmap()
      {
           printf("\n\n");
           for(int i=10;i>=1;i--)
             {
              for(int j=1;j<=15;j++) printf("%c",map[i][j]);
              printf("\n");
             }
              printf("\n\n");
      }                  
      void buildlist()
      {
         count=0;
         char temp[11][16];
         for(int i=1;i<=10;i++)
           for(int j=1;j<=15;j++)
             temp[i][j]=map[i][j];
         for(int i=1;i<=10;i++)
           for(int j=1;j<=15;j++)
             if(map[i][j])
             {
              count++;
              list[count].lh=999;
              list[count].ll=999;
              list[count].num=0;
              list[count].detect(i,j,map[i][j],map);
             }
         for(int i=1;i<=10;i++)
           for(int j=1;j<=15;j++)
             map[i][j]=temp[i][j]; 
      }
      int candel()
      {
          int lh=999,ll=999;
		  int res=2,result=0;
		  for(int i=1;i<=count;i++)
		  {
			  if(list[i].num>res||(list[i].num==res&&list[i].ll<ll)||(list[i].num==res&&list[i].ll==ll&&list[i].lh<lh))
			  {
				  res=list[i].num;
				  lh=list[i].lh;
				  ll=list[i].ll;
				  result=i;
			  }
          }
		  return result;
	  }	 
      void sub_del(int h,int l,char col)
      {
          if(h<1||h>10||l<1||l>15) return;
          else if(map[h][l]!=col) return;
          else
          {
              map[h][l]=0;
              sub_del(h+1,l,col);
              sub_del(h-1,l,col);
              sub_del(h,l+1,col);
              sub_del(h,l-1,col);
          }
     }     
      bool shiftdown()
      {
       bool flag=false;
           for(int i=1;i<=9;i++)
              for(int j=1;j<=15;j++)
                if(!map[i][j]&&map[i+1][j])
                {
                 map[i][j]=map[i+1][j];
                 map[i+1][j]=0;
                 flag=true;
                }
  //     printmap();
       return flag;
      }
      bool shiftleft()
      {
       bool flag=0;
       for(int j=1;j<=14;j++)
	   {
		   bool flag1=1,flag2=0;
		   for(int i=1;i<=10;i++)
		   {
			   if(map[i][j])
			   {
				   flag1=0;
				   break;
			   }
			   if(map[i][j+1]) flag2=1;
		   }
		   if(flag1&&flag2)
			   for(int i=1;i<=10;i++)
			   {
				   map[i][j]=map[i][j+1];
				   map[i][j+1]=0;
				   flag=1;
			   }
			   
	   }
//       printmap();    
       return flag;
      }
      void del(int num)
      {
           res[++res_c]=list[num];
           sub_del(list[num].lh,list[num].ll,list[num].col);    
          // printmap();
           while(shiftdown());
           while(shiftleft());
           buildlist();
      //    printmap();
      }
      int cul()
      {
          int total=0;
          for(int i=1;i<=res_c;i++) total+=(res[i].num-2)*(res[i].num-2);
          int remain=0;
          for(int i=1;i<=count;i++) remain+=list[i].num;
          if(!remain) total+=1000;
		  return total;
      }    
      void print()
      {
           for(int i=1;i<=res_c;i++)
           {
              printf("Move %d at (%d,%d): removed %d balls of color %c, got %d points.\n",i,res[i].lh,res[i].ll,res[i].num,res[i].col,(res[i].num-2)*(res[i].num-2));
           }
           int remain=0;
           for(int i=1;i<=count;i++) remain+=list[i].num;
           printf("Final score: %d, with %d balls remaining.\n",cul(),remain);
      } 
};
int main()
{
    int num;
    cin>>num;
    for(int j=1;j<=num;j++)
    {
     char temp[11][16],tt[2];
     for(int i=1;i<=10;i++)
       for(int k=0;k<15;k++)
         cin>>temp[i][k];
     game data(temp);
	 int dealnum;
	 cout<<"Game "<<j<<":"<<endl<<endl;
	 while(dealnum=data.candel())
	 {
		 data.del(dealnum);
	 }
	 data.print();
	 if(j!=num) cout<<endl;
	}
	return 0;
}

• Re:这道题AC的不简单。。怪我粗心。。 (0) yzhw 2009-02-16 12:51:14