Cod sursa(job #561095)

Utilizator Adela_BaciuAdela Baciu Adela_Baciu Data 18 martie 2011 20:59:16
Problema Rj Scor 100
Compilator cpp Status done
Runda matrice_bfs_dfs Marime 1.75 kb
#include<cstdio>
#include<queue>
#include<cstring>
using namespace std;

const int N = 105;
const int dlin[] = { 0 , 1 , 0 , -1 , 1 , 1 , -1 , -1 };
const int dcol[] = { 1 , 0 , -1 , 0 , 1 , -1 , 1 , -1 };

queue <pair<int , int> > q ;
pair<int , int> x , y , x0 , y0 ;
char a[N][N];
int m , n , dx[N][N] , dy[N][N];

void read()
{
	freopen ( "rj.in" , "r" , stdin );
	freopen ( "rj.out" , "w" , stdout );
	
	scanf ( "%d%d\n" , &n , &m );
	for(int i=1 ; i<=n ; ++i )
	{
		gets(1+a[i]);
		for ( int j=1 ; j<=m ; ++j)
		{
			if (a[i][j]=='R') x0 = make_pair(i,j);
			if (a[i][j]=='J') y0 = make_pair(i,j);
		}
	}
	for (int i=0 ; i<=n+1 ; ++i )
		a[i][0] = a[i][m+1] = 'X';
	for (int i=0 ; i<=m+1 ; ++i )
		a[0][i] = a[n+1][i] = 'X';
}

void solve(pair<int,int> x0,int d[N][N])
{
	q.push(x0);
	d[x0.first][x0.second] = 1;
	while (!q.empty())
	{
		x = q.front();
		q.pop();
		for (int i=0 ; i<8 ; ++i)
		{
			y.first = x.first + dlin[i];
			y.second = x.second + dcol[i];
			if (d[y.first][y.second]==0 && a[y.first][y.second]!='X')
			{
				q.push(y);
				d[y.first][y.second] = 1 + d[x.first][x.second];
			}
		}
	}
}

inline bool egale(int i, int j)
{
	return dx[i][j] == dy[i][j]; 
	if ( dx[i][j]-dy[i][j]==1 || dx[i][j]-dy[i][j]==0 || dy[i][j]-dy[i][j] == -1) return true;
	return false;
}

inline int minim(int x,int y)
{
	return x<y ? x : y;
}

void print()
{
	int min = 1<<12;
	for (int i=1 ; i<=n ; ++i )
	{
		for (int j=1 ; j<=m ; ++j)
			if ( egale(i,j) && dx[i][j]!=0 && dx[i][j]<min  ) min = dx[i][j];
	}
	for (int i=1 ; i<=n ; ++i )
	{
		for (int j=1 ; j<=m ; ++j)
		{
			if ( dx[i][j] == min && egale(i,j))
			{
				printf("%d %d %d\n" , minim(dx[i][j], dy[i][j]) , i, j );
				return;
			}
		}
	}
}

int main()
{
	read();
	solve(x0,dx);
	solve(y0,dy);
	print();
	return 0;
}