Cod sursa(job #2120684)

Utilizator marcudanfDaniel Marcu marcudanf Data 2 februarie 2018 19:29:24
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.63 kb
#include <iostream>
#include <fstream>
#include <queue>
#define inf 2e9

using namespace std;

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

queue <pair <int, int>> q1, q2;

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

int n, m, I, K, tmin = inf;
int R[105][105], J[105][105];

inline bool inrange(int x, int y){
	return (x >= 0 and x <= n) and (y >= 0 and y <= m);
}

int main(){
	char c[115];
	fin >> n >> m;
	for(int i = 0; i <= n+1; i++)
		R[i][0] = R[i][m+1] = J[i][0] = J[i][m+1] = -1;
	for(int j = 0; j <= m+1; j++)
		R[0][j] = R[n+1][j] = J[0][j] = J[n+1][j] = -1;
	fin.getline(c, 105);
	for(int i = 1; i <= n; i++){
		fin.getline(c, 105);
		for(int j = 1; j <= m; j++){
			if(c[j-1] == 'R')
				q1.push({i, j});
			else if(c[j-1] == 'J')
				q2.push({i, j});
			else if(c[j-1] == 'X')
				R[i][j] = J[i][j] = -1;
			else
				R[i][j] = J[i][j] = inf;
		}
	}
	while(!q1.empty()){
		int x = q1.front().first;
		int y = q1.front().second;
		q1.pop();
		for(int i = 0; i < 8; i++){
			int X = x + dx[i];
			int Y = y + dy[i];
			if(inrange(X, Y) and R[X][Y] > R[x][y] + 1){
				q1.push({X, Y});
				R[X][Y] = R[x][y] + 1;
			}
		}
	}
	while(!q2.empty()){
		int x = q2.front().first;
		int y = q2.front().second;
		q2.pop();
		for(int i = 0; i < 8; i++){
			int X = x + dx[i];
			int Y = y + dy[i];
			if(inrange(X, Y) and J[X][Y] > J[x][y] + 1){
				q2.push({X, Y});
				J[X][Y] = J[x][y] + 1;
			}
		}
	}
	for(int i = 1; i <= n; i++)
	for(int j = 1; j <= m; j++)
		if(R[i][j] == J[i][j] and R[i][j] > 0)
			if(tmin > R[i][j]){
				tmin = R[i][j];
				I = i;
				K = j;
			}
	fout << tmin + 1 << ' ' << I << ' ' << K;
	return 0;
}