2831365_wa.cpp

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

#include <stdio.h>
#include <algorithm>

using namespace std;

int n, t;

struct point
{
	int i, j;
};

struct snake
{
	char ch;
	point head, tail;
};

int no;
snake sna[27];
char map[100][101];
short mark[1000][1001];
int mov[][2] = {{0,1},{0,-1},{1,0},{-1,0}};
int fow[][2] = {{0,-1},{0,1},{-1,0},{1,0}};
int rig[][2] = {{-1,0},{1,0},{0,1},{0,-1}};
int lef[][2] = {{1,0},{-1,0},{0,-1},{0,1}};

int legal(int i,int j)
{
	if(i<0||j<0||i>=n||j>=n)
		return 0;
	return 1;
}

bool cmp(snake a,snake b)
{
	return a.ch<b.ch;
}

int valid(int i,int j)
{
	if(i<0||j<0||i>=n||j>=n)
		return 0;
	if(map[i][j]!='.')
		return 0;
	return 1;
}

void init()
{
	int flag;
	int i, j, k;
	int a, b;
	int s, t;

	no = 0;
	memset(mark,-1,sizeof(mark));
	for(i = 0; i < n; i++)
		for(j = 0; j < n; j++)
		{
			if(map[i][j]>='A'&&map[i][j]<='Z')
			{
				mark[i][j] = no;
				sna[no].ch = map[i][j];
				sna[no].head.i = s = i;
				sna[no].head.j = t = j;
				flag = 1;
				while(flag)
				{
					flag = 0;
					for(k = 0; k < 4; k++)
					{
						a = s+mov[k][0];b = t+mov[k][1];
						if(legal(a,b)&&mark[a][b]!=no&&map[a][b]>='a'&&map[a][b]<='z')
						{
							flag = 1;
							mark[a][b] = no;
							s = a;t = b;
							break;
						}
					}
				}
				sna[no].tail.i = s;
				sna[no].tail.j = t;
				no++;
			}
		}
		sort(sna,sna+no,cmp);
}

int get(int a,int b,char ch)
{
	int j;

	for(j = 0; j < 4; j++)
	{
			if(map[a+mov[j][0]][b+mov[j][1]]==ch)
				return j;
	}
	return -1;
}

void move()
{
	int i, j;
	int a, b;
	int c, d;

	for(i = 0; i < no; i++)
	{
		a = sna[i].head.i;
		b = sna[i].head.j;
		j = get(a,b,sna[i].ch+' ');
		c = a+fow[j][0];d = b+fow[j][1];
		if(valid(c,d))
		{
			map[c][d] = sna[i].ch;
			map[a][b] += ' ';
			map[sna[i].tail.i][sna[i].tail.j] = '.';
			sna[i].head.i = c;
			sna[i].head.j = d;
			j = get(sna[i].tail.i,sna[i].tail.j,sna[i].ch+' ');
			sna[i].tail.i += mov[j][0];
			sna[i].tail.j += mov[j][1];
			continue;
		}
		c = a+rig[j][0];d = b+rig[j][1];
		if(valid(c,d))
		{
			map[c][d] = sna[i].ch;
			map[a][b] += ' ';
			map[sna[i].tail.i][sna[i].tail.j] = '.';
			sna[i].head.i = c;
			sna[i].head.j = d;
			j = get(sna[i].tail.i,sna[i].tail.j,sna[i].ch+' ');
			sna[i].tail.i += mov[j][0];
			sna[i].tail.j += mov[j][1];
			continue;
		}
		c = a+lef[j][0];d = b+lef[j][1];
		if(valid(c,d))
		{
			map[c][d] = sna[i].ch;
			map[a][b] += ' ';
			map[sna[i].tail.i][sna[i].tail.j] = '.';
			sna[i].head.i = c;
			sna[i].head.j = d;
			j = get(sna[i].tail.i,sna[i].tail.j,sna[i].ch+' ');
			sna[i].tail.i += mov[j][0];
			sna[i].tail.j += mov[j][1];
			continue;
		}
	}
}

int main()
{
	int i;

	scanf("%d%d",&n,&t);
	for(i = 0; i < n; i++)
		scanf("%s",map[i]);
	init();
	while(t--)
		move();
	for(i = 0; i < n; i++)
		puts(map[i]);
	return 0;
}