Cod sursa(job #344790)

Utilizator prdianaProdan Diana prdiana Data 31 august 2009 16:57:43
Problema Rj Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 6.09 kb
#include <stdio.h>
#include <queue>
#include <string.h>
#define MAXN 102

using namespace std;

char h[MAXN][MAXN];
bool viz[MAXN][MAXN];
int timp[MAXN][MAXN],jl[MAXN][MAXN];

struct point
{
	int x,y;
	point()
	{
	}
	point(int v1,int v2)
	{
		x = v1;
		y = v2;
	}
};

queue<point> q;

int main()
{
	freopen("rj.in","r",stdin);
	freopen("rj.out","w",stdout);
	int n,m,i,j;
	char aux;
	point temp,jul;
	scanf("%d%d\n",&n,&m);
	for (i=1;i<=n;i++)
	{
		for (j=1;j<=m;j++)
		{
			scanf("%c",&h[i][j]);
			if (h[i][j] == 'R')
			{
				temp.x = j;
				temp.y = i;
				q.push(temp);
				viz[temp.y][temp.x] = true;
				timp[temp.y][temp.x] = 1;
			}
			if (h[i][j] == 'J')
			{
				jul.x = j;
				jul.y = i;
			}
		}
		
		scanf("%c",&aux);
	}
	int x,y;
	while (!q.empty())
	{
		x = q.front().x;
		y = q.front().y;
		if (x>1 && y>1)
		{
			if (!viz[y-1][x-1] && h[y-1][x-1] != 'X')
			{
				viz[y-1][x-1] = true;
				timp[y-1][x-1] = timp[y][x] +1;
				q.push(point(x-1,y-1));
			}
		}
		if (x>1 && y<n)
		{
			if (!viz[y+1][x-1] && h[y+1][x-1] != 'X')
			{
				viz[y+1][x-1] = true;
				timp[y+1][x-1] = timp[y][x] +1;
				q.push(point(x-1,y+1));
			}
		}
		if (x<m && y<n)
		{
			if (!viz[y+1][x+1] && h[y+1][x+1] != 'X')
			{
				viz[y+1][x+1] = true;
				timp[y+1][x+1] = timp[y][x] +1;
				q.push(point(x+1,y+1));
			}
		}
		if (x<m && y>1)
		{
			if (!viz[y-1][x+1] && h[y-1][x+1] != 'X')
			{
				viz[y-1][x+1] = true;
				timp[y-1][x+1] = timp[y][x] +1;
				q.push(point(x+1,y-1));
			}
		}
		if (x > 1)
		{
			if (!viz[y][x-1] && h[y][x-1] != 'X')
			{
				viz[y][x-1] = true;
				timp[y][x-1] = timp[y][x]+1;
				q.push(point(x-1,y));
			}
		}
		if (x<m)
		{
			if (!viz[y][x+1] && h[y][x+1] != 'X')
			{
				viz[y][x+1] = true;
				timp[y][x+1] = timp[y][x]+1;
				q.push(point(x+1,y));
			}
		}
		if (y > 1)
		{
			if (!viz[y-1][x] && h[y-1][x] != 'X')
			{
				viz[y-1][x] = true;
				timp[y-1][x] = timp[y][x]+1;
				q.push(point(x,y-1));
			}
		}
		if (y<n)
		{
			if (!viz[y+1][x] && h[y+1][x] != 'X')
			{
				viz[y+1][x] = true;
				timp[y+1][x] = timp[y][x]+1;
				q.push(point(x,y+1));
			}
		}
		q.pop();
	}
	memset(viz,0,sizeof(viz));
	q.push(jul);
	viz[jul.y][jul.x] = true;
	int best = 99999999,bx,by;
	jl[jul.y][jul.x] = 1;
	while (!q.empty())
	{
		x = q.front().x;
		y = q.front().y;
		if (x>1 && y>1 && h[y-1][x-1] != 'X')
		{
			if (!viz[y-1][x-1] )
			{
				viz[y-1][x-1] = true;
				jl[y-1][x-1] = jl[y][x] +1;
				q.push(point(x-1,y-1));
			}
			if (jl[y-1][x-1] == timp[y-1][x-1] && best>jl[y-1][x-1])
			{
				if (best == jl[y-1][x-1])
				{
					if (x-1<bx)
					{
						best = jl[y-1][x-1];
						bx = x-1;
						by = y-1;
					}
				}
				else
				{
					best = jl[y-1][x-1];
					bx = x-1;
					by = y-1;
				}
			}
		}
		if (x>1 && y<n && h[y+1][x-1] != 'X')
		{
			if (!viz[y+1][x-1] )
			{
				viz[y+1][x-1] = true;
				jl[y+1][x-1] = jl[y][x] +1;
				q.push(point(x-1,y+1));
			}
			if (jl[y+1][x-1] == timp[y+1][x-1] && best>jl[y+1][x-1])
			{
				if (best == jl[y+1][x-1])
				{
					if (x-1<bx)
					{
						best = jl[y+1][x-1];
						bx = x-1;
						by = y+1;
					}
				}
				else
				{
					best = jl[y+1][x-1];
					bx = x-1;
					by = y+1;
				}
			}
		}
		if (x<m && y<n && h[y+1][x+1] != 'X')
		{
			if (!viz[y+1][x+1] )
			{
				viz[y+1][x+1] = true;
				jl[y+1][x+1] = jl[y][x] +1;
				q.push(point(x+1,y+1));
			}
			if (jl[y+1][x+1] == timp[y+1][x+1] && best>jl[y+1][x+1])
			{
				if (best == jl[y+1][x+1])
				{
					if (x+1<bx)
					{
						best = jl[y+1][x+1];
						bx = x+1;
						by = y+1;
					}
				}
				else
				{
					best = jl[y+1][x+1];
					bx = x+1;
					by = y+1;
				}
			}
		}
		if (x<m && y>1 && h[y-1][x+1] != 'X')
		{
			if (!viz[y-1][x+1])
			{
				viz[y-1][x+1] = true;
				jl[y-1][x+1] = jl[y][x] +1;
				q.push(point(x+1,y-1));
			}
			if (jl[y-1][x+1] == timp[y-1][x+1] && best>jl[y-1][x+1])
			{
				if (best == jl[y-1][x+1])
				{
					if (x+1<bx)
					{
						best = jl[y-1][x+1];
						bx = x+1;
						by = y-1;
					}
				}
				else
				{
					best = jl[y-1][x+1];
					bx = x+1;
					by = y-1;
				}
			}
		}
		if (x > 1 && h[y][x-1] != 'X')
		{
			if (!viz[y][x-1] )
			{
				viz[y][x-1] = true;
				jl[y][x-1] = jl[y][x]+1;
				q.push(point(x-1,y));
				if (jl[y][x-1] == timp[y][x-1] && best>jl[y][x-1])
				{
					if (best == jl[y][x-1])
					{
						if (x-1<bx)
						{
							best = jl[y][x-1];
							bx = x-1;
							by = y;
						}
					}
					else
					{
						best = jl[y][x-1];
						bx = x-1;
						by = y;
					}
				}
			}
		}
		if (x<m && h[y][x+1] != 'X')
		{
			if (!viz[y][x+1] )
			{
				viz[y][x+1] = true;
				jl[y][x+1] = jl[y][x]+1;
				q.push(point(x+1,y));
				if (jl[y][x+1] == timp[y][x+1] && best>jl[y][x+1])
				{
					if (best == jl[y][x+1])
					{
						if (x+1<bx)
						{
							best = jl[y][x+1];
							bx = x+1;
							by = y;
						}
					}
					else
					{
						best = jl[y][x+1];
						bx = x+1;
						by = y;
					}
				}
			}
		}
		if (y > 1  && h[y-1][x] != 'X')
		{
			if (!viz[y-1][x])
			{
				viz[y-1][x] = true;
				jl[y-1][x] = jl[y][x]+1;
				q.push(point(x,y-1));
				if (jl[y-1][x] == timp[y-1][x] && best>jl[y-1][x])
				{
					if (best == jl[y-1][x])
					{
						if (x<bx)
						{
							best = jl[y-1][x];
							bx = x;
							by = y-1;
						}
					}
					else
					{
						best = jl[y-1][x];
						bx = x;
						by = y-1;
					}
				}
			}
		}
		if (y<n && h[y+1][x] != 'X')
		{
			if (!viz[y+1][x] )
			{
				viz[y+1][x] = true;
				jl[y+1][x] = jl[y][x]+1;
				q.push(point(x,y+1));
				if (jl[y+1][x] == timp[y+1][x] && best>jl[y+1][x])
				{
					if (best == jl[y+1][x])
					{
						if (x<bx)
						{
							best = jl[y+1][x];
							bx = x;
							by = y+1;
						}
					}
					else
					{
						best = jl[y+1][x];
						bx = x;
						by = y+1;
					}
				}
			}
		}
		q.pop();
	}
	printf("%d %d %d",best,by,bx);
	return 0;
}