2829675_tle.cpp

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

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

char map[1001][1001];
int n, t;

struct point
{
	int i, j;
};

struct snake
{
	string body;
	list <point> s;
};

int no;
snake sna[27];
int mark[1001][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 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()
{
	point tmp;
	int a, b, flag;
	int i, j, k, s, t;
	
	no = 0;
	memset(mark,0,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] = 1;
				flag = 1;
				tmp.i = s = i;tmp.j = t = j;
				sna[no].s.clear();
				sna[no].s.push_back(tmp);
				sna[no].body = "";
				sna[no].body += map[i][j];
				while(flag)
				{
					flag = 0;
					for(k = 0; k < 4; k++)
					{
						a = s+mov[k][0];b = t+mov[k][1];
						if(!mark[a][b]&&map[a][b]>='a'&&map[a][b]<='z')
						{
							tmp.i = a;tmp.j = b;
							sna[no].s.push_back(tmp);
							sna[no].body += map[a][b];
							flag = 1;
							mark[a][b] = 1;
							s = a;t = b;
							break;
						}
					}
				}
				no++;
			}
		}
}

void go()
{
	int i, j;
	int c, d;
	point a, b, tmp;
	list <point> ::iterator iter1, iter2;

	for(i = 0; i < no; i++)
	{
		iter1 = iter2 = sna[i].s.begin();
		iter2++;
		a = *iter1;b = *iter2;
		for(j = 0; j < 4; j++)
		{
			if(a.i+mov[j][0]==b.i&&a.j+mov[j][1]==b.j)
				break;
		}
		c = a.i+fow[j][0];d = a.j+fow[j][1];
		if(valid(c,d))
		{
			tmp.i = c;tmp.j = d;
			map[c][d] = 'A';
			iter1 = sna[i].s.end();
			iter1--;
			map[(*iter1).i][(*iter1).j] = '.';
			sna[i].s.pop_back();
			sna[i].s.push_front(tmp);
			continue;
		}
		c = a.i+rig[j][0];d = a.j+rig[j][1];
		if(valid(c,d))
		{
			tmp.i = c;tmp.j = d;
			map[c][d] = 'A';
			iter1 = sna[i].s.end();
			iter1--;
			map[(*iter1).i][(*iter1).j] = '.';
			sna[i].s.pop_back();
			sna[i].s.push_front(tmp);
			continue;
		}
		c = a.i+lef[j][0];d = a.j+lef[j][1];
		if(valid(c,d))
		{
			tmp.i = c;tmp.j = d;
			map[c][d] = 'A';
			iter1 = sna[i].s.end();
			iter1--;
			map[(*iter1).i][(*iter1).j] = '.';
			sna[i].s.pop_back();
			sna[i].s.push_front(tmp);
			continue;
		}
	}
}

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

void revert()
{
	int i, j;
	point t;
	list <point> ::iterator iter;

	for(i = 0; i < no; i++)
	{
		for(j = 0,iter = sna[i].s.begin(); j < sna[i].body.length(); j++,iter++)
		{
			t = *iter;
			map[t.i][t.j] = sna[i].body.at(j);
		}
	}
}

int main()
{
	int i;

	scanf("%d%d",&n,&t);
	for(i = 0; i < n; i++)
		scanf("%s",map[i]);
	init();
	sort(sna,sna+no,cmp);
	while(t--)
		go();
	revert();
	for(i = 0; i < n; i++)
		puts(map[i]);
	return 0;
}