zoj1162.cpp

最近在acm.zju.edu.cn上通过的题目的代码

#include <string.h>
#include <algorithm>
using namespace std;

char grids[13][18];
bool vst[13][18];

int n,m;

void input()
{
	m=10;
	n=15;
	int i;
	for (i=1;i<=m;++i)
		scanf("%s",grids[i]+1);
	for (i=0;i<m+2;++i)
		grids[i][0]=grids[i][n+1]=0;
	for (i=0;i<n+2;++i)
		grids[0][i]=grids[m+1][i]=0;
}

int qx[200],qy[200];
const int cx[]={0,1,0,-1},cy[]={1,0,-1,0};

int counts(const int &sx,const int &sy)
{
	int hd=0,tl=1;
	qx[0]=sx;
	qy[0]=sy;
	vst[sx][sy]=1;
	char cls=grids[sx][sy];
	int ax,ay,bx,by,i;
	while (hd<tl)
	{
		ax=qx[hd];
		ay=qy[hd];
		++hd;
		for (i=0;i<4;++i)
		{
			bx=ax+cx[i];
			by=ay+cy[i];
			if (grids[bx][by]==cls&&!vst[bx][by])
			{
				qx[tl]=bx;
				qy[tl]=by;
				++tl;
				vst[bx][by]=1;
			}
		}
	}
	return tl;
}

void clear(const int &sx,const int &sy)
{
	int hd=0,tl=1;
	qx[0]=sx;
	qy[0]=sy;
	char cls=grids[sx][sy];
	grids[sx][sy]=0;
	int ax,ay,bx,by,i;
	while (hd<tl)
	{
		ax=qx[hd];
		ay=qy[hd];
		++hd;
		for (i=0;i<4;++i)
		{
			bx=ax+cx[i];
			by=ay+cy[i];
			if (grids[bx][by]==cls)
			{
				qx[tl]=bx;
				qy[tl]=by;
				++tl;
				grids[bx][by]=0;
			}
		}
	}
}

int tcl[20];

int falls(const int &cl)
{
	int i,d=0;
	for (i=10;i;--i)
		if (grids[i][cl]) tcl[i]=i+d;
		else ++d;
	for (i=10;i;--i)
		if (grids[i][cl])
			grids[tcl[i]][cl]=grids[i][cl];
	for (i=1;i<=d;++i)
		grids[i][cl]=0;
	return 10-d;
}

int tcr[20];

void shifts()
{
	int i,d=0,t,j;
	for (i=1;i<=15;++i)
	{
		t=falls(i);
		if (t==0)
		{
			++d;
			tcr[i]=-1;
		}
		else tcr[i]=i-d;
	}
	for (i=1;i<=15;++i) if (tcr[i]>-1&&tcr[i]!=i)
	{
		for (j=1;j<=10;++j)
			grids[j][tcr[i]]=grids[j][i];
	}
	for (i=0;i<d;++i)
		for (j=1;j<=10;++j)
			grids[j][15-i]=0;
}

int work()
{
	int rd=0,i,j,ans=0,tot,tx,ty,tmp;
	printf("\n");
	while (1)
	{
		memset(vst,0,sizeof(vst));
		tot=0;
		for (j=1;j<=15;++j)
			for (i=10;i;--i)
				if (grids[i][j]&&!vst[i][j])
				{
					tmp=counts(i,j);
					if (tmp>tot)
					{
						tot=tmp;
						tx=j;
						ty=i;
					}
				}
		if (tot<2) return ans;
		++rd;
		printf("Move %d at (%d,%d): removed %d balls of color %c, got %d points.\n",rd,11-ty,tx,tot,grids[ty][tx],(tot-2)*(tot-2));
		ans+=(tot-2)*(tot-2);
		clear(ty,tx);
		shifts();
	}
	return 0;
}

void output()
{
	int ans=work();
	int lefts=0,i,j;
	for (i=1;i<=10;++i)
		for (j=1;j<=15;++j)
			if (grids[i][j]) ++lefts;
	if (lefts==0) ans+=1000;
	printf("Final score: %d, with %d balls remaining.\n",ans,lefts);
}

int main()
{
	int cs,i;
int cases; scanf("%d", &cases);
bool first = true;
while (cases--){
    if (first) first = false; else puts("");
	scanf("%d",&cs);
	for (i=1;i<=cs;++i)
	{
		input();
		if (i>1) printf("\n");
		printf("Game %d:\n",i);
		output();
	}
}
	return 0;
}