2830886_wa.cpp

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

#include <stdio.h>
#include <algorithm>
#define INIT (point *)malloc(sizeof(point))
using namespace std;

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

struct point
{
	int i, j;
	point *next, *prev;
};

struct snake
{
	int len;
	char str[500000];
	point *head, *tail;
};

int no;
int index[27];
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;
}

int legal(int i,int j)
{
	if(i<0||j<0||i>=n||j>=n)
		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].head = INIT;
				sna[no].head->next = sna[no].head->prev = NULL;
				tmp = INIT;
				sna[no].len = 0;
				tmp->i = s = i;tmp->j = t = j;
				sna[no].str[sna[no].len++] = map[i][j];
				tmp->next = sna[no].head->next;
				sna[no].head->next = tmp;
				tmp->prev = sna[no].head;
				sna[no].tail = sna[no].head->next;
				//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(legal(a,b)&&!mark[a][b]&&map[a][b]>='a'&&map[a][b]<='z')
						{
							tmp = INIT;
							tmp->i = a;tmp->j = b;
							//tmp->ch = map[a][b];
							sna[no].str[sna[no].len++] = map[a][b];
							//tmp.i = a;tmp.j = b;
							//sna[no].s.push_back(tmp);
							tmp->next = sna[no].tail->next;
							sna[no].tail->next = tmp;
							tmp->prev = sna[no].tail;
							sna[no].tail = sna[no].tail->next;
							//sna[no].body += map[a][b];
							flag = 1;
							mark[a][b] = 1;
							s = a;t = b;
							break;
						}
					}
				}
				sna[no].str[sna[no].len] = '\0';
				no++;
			}
		}
}

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

	changed = 0;
	for(i = 0; i < no; i++)
	{
		//iter1 = iter2 = sna[i].s.begin();
		//iter2++;
		//a = *iter1;b = *iter2;
		I = i;
		i = index[i];
		a = sna[i].head->next;
		b = a->next;
		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 = INIT;
			tmp->i = c;tmp->j = d;
			map[c][d] = 'A';
			//iter1 = sna[i].s.end();
			//iter1--;
			//sna[i].tail = sna[i].tail->prev;
			//sna[i].tail->next = NULL;
			map[sna[i].tail->i][sna[i].tail->j] = '.';
			sna[i].tail = sna[i].tail->prev;
			sna[i].tail->next = NULL;
			sna[i].head->next->prev = tmp;
			tmp->prev = sna[i].head;
			tmp->next = sna[i].head->next;
			sna[i].head->next = tmp;
			//sna[i].s.pop_back();
			//sna[i].s.push_front(tmp);
			changed = 1;
			i = I;
			continue;
		}
		c = a->i+rig[j][0];d = a->j+rig[j][1];
		if(valid(c,d))
		{
			tmp = INIT;
			tmp->i = c;tmp->j = d;
			map[c][d] = 'A';
			//iter1 = sna[i].s.end();
			//iter1--;
			//sna[i].tail = sna[i].tail->prev;
			//sna[i].tail->next = NULL;
			map[sna[i].tail->i][sna[i].tail->j] = '.';
			sna[i].tail = sna[i].tail->prev;
			sna[i].tail->next = NULL;
			sna[i].head->next->prev = tmp;
			tmp->prev = sna[i].head;
			tmp->next = sna[i].head->next;
			sna[i].head->next = tmp;
			//sna[i].s.pop_back();
			//sna[i].s.push_front(tmp);
			changed = 1;
			i = I;
			continue;
		}
		c = a->i+lef[j][0];d = a->j+lef[j][1];
		if(valid(c,d))
		{
			tmp = INIT;
			tmp->i = c;tmp->j = d;
			map[c][d] = 'A';
			//iter1 = sna[i].s.end();
			//iter1--;
			//sna[i].tail = sna[i].tail->prev;
			//sna[i].tail->next = NULL;
			map[sna[i].tail->i][sna[i].tail->j] = '.';
			sna[i].tail = sna[i].tail->prev;
			sna[i].tail->next = NULL;
			sna[i].head->next->prev = tmp;
			tmp->prev = sna[i].head;
			tmp->next = sna[i].head->next;
			sna[i].head->next = tmp;
			//sna[i].s.pop_back();
			//sna[i].s.push_front(tmp);
			changed = 1;
			i = I;
			continue;
		}
		i = I;
	}
	return changed;
}

bool cmp(int a,int b)
{
	return strcmp(sna[a].str,sna[b].str)<0;
}

void revert()
{
	int i, j;
	point *t;

	for(i = 0; i < no; i++)
	{
		t = sna[i].head->next;
	//	printf("\nlen = %d\n",sna[i].len);
	//	while(t)
	//	{
	//		printf("Y");
	//		t = t->next;
	//	}
	//	printf("\n");
		for(j = 0; j < sna[i].len; j++)
		{
			map[t->i][t->j] = sna[i].str[j];
			t = t->next;
		}
	}
	for(i = 0; i < n; i++)
		puts(map[i]);
//	printf("\n");
//	system("pause");
}

int main()
{
	int i, t;

	freopen("data.txt","r",stdin);
	freopen("res.txt","w",stdout);
	scanf("%d%d",&n,&t);
	for(i = 0; i < n; i++)
		scanf("%s",map[i]);
	init();
//	revert();
	for(i = 0; i < no; i++)
		index[i] = i;
	//sort(sna,sna+no,cmp);
	sort(index,index+no,cmp);
	while(t--&&go());
	revert();
	return 0;
}