3027049_ac_342ms_152k.c

北大大牛代码 1240道题的原代码 超级权威

#include <stdio.h>
#include <string.h>

char map[10][16];
int visited[10][16];
typedef struct node
{
	int i, j;
}type;

int valid(int i,int j)
{
	if(i < 0 || j < 0 || i > 9 || j > 14)
		return 0;
	return 1;
}

int bfs(int i,int j)
{
	type t, q;
	type que[160];
	int f, r, l, ret;
	int ii, jj;
	int mov[][2] = {{0,1},{0,-1},{1,0},{-1,0}};

	f = r = -1;
	t.i = i;
	t.j = j;
	que[++r] = t;
	visited[i][j] = 1;
	ret = 1;
	while(f!=r)
	{
		++f;
		t = que[f];
		for(l = 0; l < 4; l++)
		{
			ii = t.i+mov[l][0];
			jj = t.j+mov[l][1];
			if(valid(ii,jj)&&!visited[ii][jj]&&map[ii][jj]==map[i][j])
			{
				visited[ii][jj] = 1;
				ret++;
				q.i = ii;q.j = jj;
				que[++r] = q;
			}
		}
	}
	return ret;
}

void down()
{
	int i, j, l, k;
	char tmp[11];

	for(j = 0; j < 15; j++)
	{
		l = 0;
		for(i = 9; i >= 0; i--)
		{
			if(map[i][j]!=' ')
			{
				tmp[l++] = map[i][j];
				map[i][j] = ' ';
			}
		}
		for(i = 9, k = 0; k < l; i--,k++)
		{
			map[i][j] = tmp[k];
		}
	}
}

void copycol(int a,int b)
{
	int i;

	for(i = 0; i < 10; i++)
	{
		map[i][a] = map[i][b];
	}
}

void left()
{
	int i, j, k, l;
	int tmp[16], col[16];

	for(i = 0; i < 15; i++)
	{
		k = 1;
		for(j = 0; k && j < 10; j++)
		{
			if(map[j][i]!=' ')
			{
				k = 0;
			}
		}
		tmp[i] = k;
	}
	l = 0;
	for(i = 0; i < 15; i++)
	{
		if(tmp[i]==0)
		{
			col[l++] = i;
		}
	}
	for(i = 0, k = 0; k < l; k++, i++)
	{
		if(i!=col[k])
		{
			copycol(i,col[k]);
		}
	}
	for(i = l; i < 15; i++)
	{
		for(j = 0; j < 10; j++)
		{
			map[j][i] = ' ';
		}
	}
}

void erase(int i,int j)
{
	type t, q;
	type que[160];
	int f, r, l;
	int ii, jj;
	char ch;
	int mov[][2] = {{0,1},{0,-1},{1,0},{-1,0}};

	ch = map[i][j];
	f = r = -1;
	t.i = i;
	t.j = j;
	que[++r] = t;
	while(f!=r)
	{
		++f;
		t = que[f];
		for(l = 0; l < 4; l++)
		{
			ii = t.i+mov[l][0];
			jj = t.j+mov[l][1];
			if(valid(ii,jj)&&map[ii][jj]==ch)
			{
				map[ii][jj] = ' ';
				q.i = ii;q.j = jj;
				que[++r] = q;
			}
		}
	}
}

int main()
{
	int i, j, max;
	int r, c, m;
	int now, cas, end;
	int tot, no, score;
	char ch;

	scanf("%d",&cas);
	for(now = 1; now <= cas; now++)
	{
		printf("Game %d:\n\n",now);
		end = 0;
		score = 0;
		tot = 150;
		for(i = 0; i < 10; i++)
		{
			scanf("%s",map[i]);
		}
		no = 1;
		while(!end)
		{
			memset(visited,0,sizeof(visited));
			max = -1;
			for(j = 0; j < 15; j++)
			{
				for(i = 9; i >= 0; i--)
				{
					if(!visited[i][j]&&map[i][j]!=' ')
					{
						m = bfs(i,j);
						if(m > max)
						{
							ch = map[i][j];
							max = m;
							r = i;
							c = j;
						}
					}
				}
			}
			if(max==1)
			{
				end = 1;
			}
			else
			{
				tot -= max;
				if(tot==0)
				{
					end = 1;
					score += 1000;
				}
				erase(r,c);
				down();
				left();
				score += (max-2)*(max-2);
				printf("Move %d at (%d,%d): removed %d balls of color %c, got %d points.\n",no++,10-r,c+1,max,ch,(max-2)*(max-2));
			}
		}
		printf("Final score: %d, with %d balls remaining.\n\n",score,tot);
	}
	return 1;
}