Cod sursa(job #2150236)

Utilizator Dobricean_IoanDobricean Ionut Dobricean_Ioan Data 3 martie 2018 12:59:34
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.52 kb
#include <queue>
#include <fstream>
#include <tuple>

using namespace std;

ifstream fin ( "rj.in" );
ofstream fout ( "rj.out" );

const int Dim = 101;
const int di[]={0, 1, 0, -1, -1, 1, -1, 1},
			  dj[]={1, 0, -1, 0, -1, 1,  1,-1};
int n,m , DR[Dim][Dim],ij,cj,ir,jr , DJ[Dim][Dim];
char A[Dim][Dim];
queue < pair < int , int > > Q;
void Lee( int is,int js, int D[Dim][Dim]);

int main() {

	fin >> n >> m;
	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';
	fin.get();
	char c;
	for ( int i = 1; i <= n; ++i) {
		for ( int j = 1; j <= m; ++j) {
			fin.get(c);
		if ( c == 'J' ) {
			ij = i , cj = j;
			A[i][j] = ' ';
			}
		else
		if ( c == 'R' ) {
			ir = i , jr = j;
			A[i][j] = ' ';
			}
		else
		A[i][j] = c;
		}
    fin.get();
    }
  	Lee(ir,jr,DR);
	Lee(ij,cj,DJ);

	int mi = 0x3f3f3f3f,  x, y;
	for (int i = 1; i <= n; ++i)
		for (int j = 1; j <= m; ++j)
			if (DR[i][j] == DJ[i][j])
				if (DR[i][j] < mi and DR[i][j] != -1) {
					mi = DR[i][j];
					x = i;
					y = j;
					}
	fout << mi <<' '<< x << ' ' << y;
}

void Lee( int is,int js, int D[Dim][Dim]) {

	for (int i = 0; i <= n+1; ++i)
	for (int j = 0; j <= m+1; ++j)
		D[i][j] = -1;
	D[is][js] = 1;
	Q.push({is,js});
	int fi,fj;
	while (!Q.empty()) {
		 tie(fi,fj) = Q.front();
		 Q.pop();
		 for (int i = 0; i < 8 ; ++i)
			if (A[fi + di[i]][fj + dj[i]] == ' ' and D[fi + di[i]][fj + dj[i]] == -1 ) {
                D[fi + di[i]][fj + dj[i]] = 1 + D[fi][fj];
				Q.push( {fi + di[i] , fj + dj[i] } );
				}
		}
}