Cod sursa(job #1278571)

Utilizator o_micBianca Costin o_mic Data 29 noiembrie 2014 01:51:54
Problema Rj Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.44 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#define x first
#define y second

using namespace std;
 
vector <string> v;
int distr[105][105], distj[105][105];;
int n, m;

int is_inside(int x, int y){
	return (x >= 0 && x < n && y >= 0 && y < m);
}

void bfs(pair <int, int> romeo, int a[105][105]){
	queue <pair <int, int> > c;
	a[romeo.x][romeo.y] = 1;
	for(c.push(romeo); !c.empty(); c.pop()){
		pair <int, int> fr = c.front();
		for(int i = -1; i <= 1; i++)
			for(int j = -1; j <= 1; j++){
				int ii = fr.x + i, jj = fr.y + j;
				if(is_inside(ii, jj) && !a[ii][jj] && v[ii][jj] != 'X'){
						c.push(make_pair(ii, jj));
						a[ii][jj] = a[fr.x][fr.y] + 1;
				}
			}
	}
}

pair <int, int> find(char c){
	for(int i = 0; i < n; i++)
		for(int j = 0; j < m; j++)
			if(v[i][j] == c)
				return make_pair(i, j);
}

int main() {
	freopen("rj.in", "r", stdin);
	freopen("rj.out", "w", stdout);
	cin.sync_with_stdio(false);
	cin >> n >> m;
	cin.get();
	for(int i = 0; i < n; i++){
		string s;
		getline(cin, s);
		v.push_back(s);
	}
	bfs(find('R'), distr);
	bfs(find('J'), distj);
	pair <int, int> j = find('J');
	pair <int, int> minp = j;
	int minn = distr[j.x][j.y];
	for(int i = 0; i < n; i++)
		for(int j = 0; j < m; j++)
			if(max(distr[i][j], distj[i][j]) < minn && v[i][j]!='X' && distr[i][j]){
				minn = max(distr[i][j], distj[i][j]);
				minp = make_pair(i, j);
			}
	cout << minn << " " << minp.x + 1 << " " << minp.y + 1;
	return 0;
}