Cod sursa(job #2375161)

Utilizator TincaMateiTinca Matei TincaMatei Data 7 martie 2019 22:40:40
Problema Rj Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.8 kb
#include <bits/stdc++.h>

using namespace std;

char getnext(FILE *fin) {
	char ch = fgetc(fin);
	while(ch == '\n')
		ch = fgetc(fin);
	return ch;
}

const int MAX_N = 100;
char matr[1+MAX_N+1][1+MAX_N+1];
int dp[2][1+MAX_N+1][1+MAX_N+1];

int dl[] = {0, 1, 1, 1, 0,-1,-1,-1};
int dc[] = {1, 1, 0,-1,-1,-1, 0, 1};

void bfs(int lr, int cr, int lj, int cj) {
	deque<pair<int, pair<int, int> > > q;
	
	dp[0][lr][cr] = dp[1][lj][cj] = 1;
	
	q.push_back(make_pair(0, make_pair(lr, cr)));
	q.push_back(make_pair(1, make_pair(lj, cj)));

	while(!q.empty()) {
		int r = q.front().first;
		int l = q.front().second.first;
		int c = q.front().second.second;

		q.pop_front();

		for(int i = 0; i < 8; ++i) {
			int ln = l + dl[i];
			int cn = c + dc[i];

			if(matr[ln][cn] == ' ' && dp[r][ln][cn] == 0) {
				dp[r][ln][cn] = dp[r][l][c] + 1;
				q.push_back(make_pair(r, make_pair(ln, cn)));
			}
		}
	}
}

int main() {
#ifdef HOME
	FILE *fin = fopen("input.in", "r");
	FILE *fout = fopen("output.out", "w");
#else
	FILE *fin = fopen("rj.in", "r");
	FILE *fout = fopen("rj.out", "w");
#endif

	int n, m;
	int lr, cr, lj, cj;
	int lrez, crez, rez;
	fscanf(fin, "%d%d", &n, &m);
	lr = cr = lj = cj = 0;
	for(int l = 1; l <= n; ++l)
		for(int c = 1; c <= m; ++c) {
			matr[l][c] = getnext(fin);
			if(matr[l][c] == 'R') {
				lr = l;
				cr = c;
				matr[l][c] = ' ';
			} else if(matr[l][c] == 'J') {
				lj = l;
				cj = c;
				matr[l][c] = ' ';
			}
		}
	
	bfs(lr, cr, lj, cj);

	lrez = crez = rez = 1000000000;

	for(int l = 1; l <= n; ++l)
		for(int c = 1; c <= m; ++c) {
			int cost = max(dp[0][l][c], dp[1][l][c]);
			if(dp[0][l][c] != 0 && dp[1][l][c] != 0 && dp[0][l][c] == dp[1][l][c] && cost < rez) {
				rez = cost;
				lrez = l;
				crez = c;
			}
		}

	fprintf(fout, "%d %d %d", rez, lrez, crez);

	fclose(fin);
	fclose(fout);
	return 0;
}