921519_10274.cpp

ACM 10274 Fans and Gems

#include <stdio.h>
#include <string.h>
/*Fans and Gems  */
#define nums 45000
#define maxspace 240
typedef struct map_type
{
	char R, G, B, step;
	char map[12][20];
	char move[20];
}mapp;

int n, m;
int pos[maxspace][2];
int factor[maxspace];
int space;


mapp visited[nums];
mapp queue[50000];
mapp original;
int top;
char path[20];
 
void compute_factor()
{
	int i;
	factor[0] = 1;
	factor[1] = 2;
	factor[2] = 3;

	for(i = 3 ; i < maxspace ; i++)
		factor[i] = (factor[i - 1] + factor[i - 2]) % nums;
}

int tonum(char ch)
{
	if(ch == ' ')
		return 0;
	else if(ch == '1')
		return 1;
	else if(ch == '2')
		return 2;
	else if(ch == '3')
		return 3;
	else if(ch == '@')
		return 4;
	return -1;
}

int hash(mapp *p)
{
	int i;
	int value;
	value = 0;
	for(i = 0 ; i < space ; i++)
	{
		value += tonum(p->map[pos[i][0]][pos[i][1]]) * factor[i];
		value = value % nums;
	}
	return value;
}

void show(mapp *p)
{
	int i, j;
	for(i = 0 ; i < n ; i++)
	{
		for(j = 0 ; j < m ; j++)
			printf("%c",p->map[i][j]);
		printf("\n");
	}
	printf("%d %d %d\n",p->R, p->G, p->B);
}


int equal(mapp *p, mapp *q)
{
	int i, j;
	if(p->R != q->R || p->G != q->G || p->B != q->B)
		return -1;
	for(i = 0 ; i < n ; i++)
		for(j = 0 ; j < m ; j++)
			if(p->map[i][j] != q->map[i][j])
				return -1;
	return 1;
}

int Isvisited(mapp *p)
{
	int index = hash(p);

	if(visited[index].step == -1)
		return index;
	if(equal(p, &visited[index]) == -1)
		return index;

	return -1;
}

int disappear(mapp *p)
{
	int i, j, k;
	char visited[14][22];
	int queue[240][2];
	int front, rear;
	char key;
	int gems[3], temp;
	int nowx, nowy;
	int Isdisappear;
	int indexx[4] = {1, -1, 0, 0};
	int indexy[4] = {0, 0, 1, -1};
	memset(visited, 0, sizeof(visited));

	gems[0] = p->R;
	gems[1] = p->G;
	gems[2] = p->B;

	Isdisappear = 0;
	for(i = 0 ; i < n ; i++)
		for(j = 0 ; j < m ; j++)
			if(visited[i][j] == 0)
			{
				if(p->map[i][j] >= '1' && p->map[i][j] <= '3')
				{
					key = p->map[i][j];
					if(p->map[i + 1][j] == key || p->map[i - 1][j] == key 
						|| p->map[i][j + 1] == key || p->map[i][j - 1] == key)
					{
						Isdisappear = 1;
						front = rear = 0;
						queue[rear][0] = i;
						queue[rear][1] = j;
						p->map[i][j] = ' ';
						rear++;
						temp = gems[key - '1'] - 1;
						while(front < rear)
						{
							nowx = queue[front][0];
							nowy = queue[front][1];
							front++;
							for(k = 0 ; k < 4 ; k ++)
								if(p->map[nowx + indexx[k]][nowy + indexy[k]] == key)
								{
									temp--;
									p->map[nowx + indexx[k]][nowy + indexy[k]] = ' ';
									queue[rear][0] = nowx + indexx[k];
									queue[rear][1] = nowy + indexy[k];
									rear++;
								}
						}
						gems[key - '1'] = temp;
					}
				}
			}
	p->R = gems[0];
	p->G = gems[1];
	p->B = gems[2];
	return Isdisappear;
}

void movegems(mapp *p, char direct)
{
	int i, j;
	int k;
	int Ismove;
	Ismove = 1;
	if(direct == 'D')
	{
		while(Ismove == 1)
		{
			Ismove = 0;
			for(j = 0 ; j < m ; j++)
			{
				k = -1;
				for(i = n - 1 ; i >= 0 ; i--)
				{
					if(p->map[i][j] == '#')
						k = -1;
					else if(p->map[i][j] == ' ' && p->map[i + 1][j] != ' ')
						k = i;
					else if(p->map[i][j] != '#' && p->map[i][j] !=' ')
						if(k != -1)
						{
							Ismove = 1;
							p->map[k][j] = p->map[i][j];
							p->map[i][j] = ' ';
							k--;
						}
				
				}
			}
			if(Ismove == 1)
				Ismove = disappear(p);
		}
	}
	else if(direct == 'L')
	{
		while(Ismove == 1)
		{
			Ismove = 0;
			for(i = 0 ; i < n ; i++)
			{
				k = -1;
				for(j = 0 ; j < m ; j++)
				{
					if(p->map[i][j] == '#')
						k = -1;
					else if(p->map[i][j] == ' ' && p->map[i][j - 1] != ' ')
						k = j;
					else if(p->map[i][j] != '#' && p->map[i][j] !=' ')
						if(k != -1)
						{
							Ismove = 1;
							p->map[i][k] = p->map[i][j];
							p->map[i][j] = ' ';
							k++;
						}
				}
			}
			if(Ismove == 1)
				Ismove = disappear(p);
		}

	}
	else if(direct == 'R')
	{
		while(Ismove == 1)
		{
			Ismove = 0;
			for(i = 0 ; i < n ; i++)
			{
				k = -1;
				for(j = m - 1 ; j >= 0 ; j--)
				{
					if(p->map[i][j] == '#')
						k = -1;
					else if(p->map[i][j] == ' ' && p->map[i][j + 1] != ' ')
						k = j;
					else if(p->map[i][j] != '#' && p->map[i][j] !=' ')
						if(k != -1)
						{
							Ismove = 1;
							p->map[i][k] = p->map[i][j];
							p->map[i][j] = ' ';
							k--;
						}
				}
			}
			
			if(Ismove == 1)
				Ismove = disappear(p);
		}
	}
	else if(direct == 'U')
	{
		while(Ismove == 1)
		{
			Ismove = 0;
			for(j = 0 ; j < m ; j++)
			{
				k = -1;
				for(i = 0 ; i < n ; i++)
				{
					if(p->map[i][j] == '#')
						k = -1;
					else if(p->map[i][j] == ' ' && p->map[i - 1][j] != ' ')
						k = i;
					else if(p->map[i][j] != '#' && p->map[i][j] !=' ')
						if(k != -1)
						{
							Ismove = 1;
							p->map[k][j] = p->map[i][j];
							p->map[i][j] = ' ';
							k++;
						}
				}
			}
			if(Ismove == 1)
				Ismove = disappear(p);
		
		}
	}
}
void trace(mapp *p, char *str)
{
	int i;

	for(i = 0 ; str[i] ; i++)
	{
		movegems(p, str[i]);
		show(p);
	}
}
int BFS()
{
	int front, rear;
	int t;
	int i;
	char direction[4] = {'D','L','R','U'};
	mapp now;
	mapp temp;
	
	front = rear = top = 0;
	queue[rear++] = original;
	visited[hash(&original)] = original;

	while(front < rear)
	{	
		now = queue[front++];

		if(now.B != 1 && now.G != 1 && now.R != 1)
		{
			for(i = 0 ; i < 4 ; i++)
			{
			
					temp = now;
					movegems(&temp,direction[i]);
					if((temp.R + temp.G + temp.B) == 0)
					{
						strcpy(path, now.move);
						path[now.step] = direction[i];
						path[now.step + 1] =  '\0';
						return now.step + 1;
					}

					temp.step = now.step + 1;

					if(temp.step < 18)
					{	
						t = Isvisited(&temp);
						if(t > -1)
						{
							strcpy(temp.move, now.move);
							temp.move[now.step] = direction[i];
							temp.move[now.step + 1] = '\0';
							queue[rear++] = temp;
							visited[t] = temp;
						}
					}
			
			}
		}
	}
	return -1;
}

int main()
{
	int i, j;
	int cas;
	int r,g,b;
	int ans;
	char st[1000];
	freopen("10274.txt","r",stdin);
//	freopen("10274o.txt","w",stdout);
	compute_factor();
	scanf("%d",&cas);
	while(cas > 0)
	{
		cas--;
		space = 0;
		scanf("%d%d", &n, &m);
		r = g = b = 0;
		for(i = 0 ; i < nums ; i++)
			visited[i].step = -1;
		for(i = 1 ; i <= n ; i++)
		{
			gets(st);
			for(j = 1 ; j <= m ; j++)
			{	
				scanf("%c",&(original.map[i][j]));
				if(original.map[i][j] != '#')
				{
					pos[space][0] = i;
					pos[space][1] = j;
					space++;
				}
				if(original.map[i][j] == '1')
					r++;
				else if(original.map[i][j] == '2')
					g++;
				else if(original.map[i][j] == '3')
					b++;
			}
		}
	/*
		m += 2;
		n += 2;
		for(i = 0 ; i < n ; i++)
			original.map[i][0] = original.map[i][m - 1] = '#';
		
		for(j = 0 ; j < m ; j++)
			original.map[0][j] = original.map[n - 1][j] = '#';
*/
		gets(st);
		gets(st);

		original.R = r;
		original.G = g;
		original.B = b;

		original.step = 0;
		original.move[0] = '\0';
		ans = 0;
//		show(&original);
//		trace(&original, "LD");

		ans = BFS();
		if(ans == -1)
			puts("-1");
		else
			puts(path);		

	}
	return 0;
}