Cod sursa(job #1474695)

Utilizator StarGold2Emanuel Nrx StarGold2 Data 22 august 2015 16:42:18
Problema Rj Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.53 kb
#include <cstdio>
#include <cstring>
#include <algorithm>

#define DIM 128
#define INF ((1LL<<31)-1)

using namespace std;

int ri, rj, ji, jj, N, M;
int minim = INF, Lmin, Cmin;

int A[DIM][DIM][3];
int C[DIM *DIM][3]; 

char S[DIM];

int Di[9] = {0,-1,-1,-1, 0, 1, 1, 1, 0};
int Dj[9] = {0,-1, 0, 1, 1, 1, 0,-1,-1};

void BFS(int is, int js, int pos){
	
	int P = 1, U = 1;
	
	C[1][1] = is;
	C[1][2] = js;
	
	while(P <= U){
		
		int ic = C[P][1];
		int jc = C[P][2];
		
		for(int d = 1; d <= 8; d ++){
			
			int iv = ic + Di[d];
			int jv = jc + Dj[d];
			
			if(iv >= 1 && iv <= N)
				if(jv >= 1 && jv <= M)
					if(A[iv][jv][pos] == 0){
						
						U ++;
						C[U][1] = iv;
						C[U][2] = jv;
						A[iv][jv][pos] = A[ic][jc][pos] + 1;
					}
		}
		
		P ++;
	}
	
	return;
}

int main(){
	
	freopen("rj.in" ,"r", stdin );
	freopen("rj.out","w", stdout);
	
	scanf("%d %d", &N, &M);
	
	for(int i = 1; i <= N; i ++){
		fgets(S + 1, DIM, stdin);
		
		for(int j = 1; j <= M; j ++){
			
			if(S[j] == 'R'){
				
				ri = i;
				rj = j;
				A[i][j][1] = 1;
			}
			
			if(S[j] == 'J'){
				
				ji = i;
				jj = j;
				A[i][j][2] = 1;
			}
			
			if(S[j] == 'X'){
				
				A[i][j][1] = -1;
				A[i][j][2] = -1; 
			}
		}
	}
	
	BFS(ri, rj, 1);
	BFS(ji, jj, 2);
	
	for(int i = 1; i <= N; i ++)
		for(int j = 1; j <= M; j ++)
			if(A[i][j][1] == A[i][j][2] && A[i][j][1] != -1)
				if(minim > A[i][j][1]){
					
					Lmin = i;
					Cmin = j;
					minim = A[i][j][1];
				}
				
	printf("%d %d %d", minim, Lmin, Cmin);
	
	fclose(stdin );
	fclose(stdout);
	
	return 0;
}