Cod sursa(job #867449)

Utilizator matei_cChristescu Matei matei_c Data 29 ianuarie 2013 18:25:48
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.16 kb
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cassert>
#include<vector>
using namespace std ;

#define maxn 101
#define maxcoada 10001
#define maxdir 8

struct punct
{
	int x, y ;
};

int dx[maxdir] = { 0, 1,  0, -1, -1, 1, -1,  1 } ;
int dy[maxdir] = { 1, 0, -1,  0, -1, 1,  1, -1 } ; 

int n, m ;
char harta[maxn][maxn] ;

int xr, yr ;
int xj, yj ;

int romeo[maxn][maxn] ;
int julieta[maxn][maxn] ;

void lee(int xs, int ys, int dist[maxn][maxn] )
{
	
	punct coada[maxcoada] ;
	
	for(int i = 0; i <= n + 1; ++i )
		for(int j = 0; j <= m + 1 ; ++j )
			dist[i][j] = -1 ;
	
	int len = 0 ;

	coada[len].x = xs ;
	coada[len].y = ys ;
	dist[xs][ys] = 1 ;

	for(int i = 0; i <= len; ++i )
	{
		int xn = coada[i].x ;
		int yn = coada[i].y ;		
		
		for(int j = 0; j < maxdir; ++j )
		{
			int xact = xn + dx[j] ;
			int yact = yn + dy[j] ;			
			
			if( harta[ xact ][ yact ] == ' ' && dist[ xact ][ yact ] == -1 )
			{
				dist[ xact ][ yact ] = dist[xn][yn] + 1 ;
				++len ;
				coada[len].x = xact ;
				coada[len].y = yact ;
			}
		}	
	}
}

int main()
{
	
	freopen("rj.in", "r", stdin);
	freopen("rj.out", "w", stdout);
	
	scanf("%d%d\n", &n, &m);
	
	for(int i = 0; i <= n + 1; ++i )
		harta[i][0] = harta[i][ m + 1 ] = 'X' ;
	
	for(int i = 0; i <= m + 1; ++i )
		harta[0][i] = harta[ n + 1 ][i] = 'X' ;
	
	for(int i = 1; i <= n; ++i )
	{
		char ch ;
		
		for(int j = 1; j <= m; ++j )
		{
			scanf("%c", &ch);
			harta[i][j] = ch ;
			
			if( harta[i][j] == 'R' )
			{
				xr = i ;
				yr = j ;
				harta[i][j] = ' ' ;
			}
			
			if( harta[i][j] == 'J' )
			{
				xj = i ;
				yj = j ;
				harta[i][j] = ' ' ;
			}
		}
		
		scanf("%c", &ch);
		
	}
	
	lee( xr, yr, romeo ) ;
	
	lee( xj, yj, julieta ) ;
	
	int tmin = maxcoada ;
	int xmin, ymin ;

	for(int i = 1; i <= n; ++i )
	{
		for(int j = 1; j <= m; ++j )
		{
			if( romeo[i][j] == julieta[i][j] )
			{
				if( romeo[i][j] < tmin && romeo[i][j] != -1 )
				{
					tmin = romeo[i][j] ;
					xmin = i ;
					ymin = j ;
				}	
			}	
		}	
	}	
	
	printf("%d %d %d\n", tmin, xmin, ymin);
	
	return 0 ;
	
}