Cod sursa(job #686830)

Utilizator samuelbumbarSamuel Bumbar samuelbumbar Data 21 februarie 2012 21:41:21
Problema Rj Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.37 kb
#include<fstream>
#include<iomanip>
#define M 102
using namespace std;
ifstream f ("rj.in");
ofstream g ("rj.out");
int a[M][M], b[M][M], bb[M][M], i, j, n, ef, m, len, ij, jr, jj, ir, soli, solj, mini;
int diri[] = {0, -1, -1, 0, 1, 1, 1, 0, -1}; //N NE E SE S SV V NV
int dirj[] = {0, 0, 1, 1, 1, 0, -1, -1, -1};
string s;  int c[100000];
void LeeRomeo() {
	int i, j, i_i, j_j, p, u, el, d;
	i = ir; j = jr; b[i][j] = 1;
	c[1] = i * 1000 + j; p = 1; u = 1; //p -primul  u -ultim
	while (p <= u) {
		el = c[p]; i = el / 1000; j = el % 1000; p++; //se codifica i,j  intr-un singur numar ex:  23, 45=>23045
		for (d = 1; d <= 8; d++) { //merge dupa cele 8 directii
			i_i = i + diri[d]; j_j = j + dirj[d]; //i_i, j_j noile pozitii ce rezulta din deplasarea din cele 8 directii
			if (b[i_i][j_j] == 0) {
				b[i_i][j_j] = b[i][j] + 1; //marcheaza celula
				u++; c[u] = i_i * 1000 + j_j; //pune in coada
			}
		}
	}
}
void LeeJulieta() {
	int i, j, i_i, j_j, p, u, el, d;
	i = ij; j = jj; bb[i][j] = 1;
	c[1] = i * 1000 + j; p = 1; u = 1;
	while (p <= u) {
		el = c[p]; i = el / 1000; j = el % 1000; p++;
		for (d = 1; d <= 8; d++) {
			i_i = i + diri[d]; j_j = j + dirj[d];
			if (bb[i_i][j_j] == 0) {
				bb[i_i][j_j] = bb[i][j] + 1;
				u++;
				c[u] = i_i * 1000 + j_j;
			}
		}
	}
}
int main()
{
	f >> n >> m; f.get();
	for (i = 0; i <= n + 1; i++) {a[i][0] = -1; a[i][m+1] = -1; } //bordare
	for (i = 0; i <= m + 1; i++) {a[0][i] = -1; a[n+1][i] = -1; } //bordare
	for (i = 1; i <= n; i++) {
		getline (f, s);
		len = s.size();
		for (j = 0; j < len; j++) {
			if (s[j] == 'X') a[i][j+1] = -1;
			if (s[j] == ' ') a[i][j+1] = 0;
			if (s[j] == 'R') ir = i, jr = j + 1;
			if (s[j] == 'J') ij = i, jj = j + 1;
		}
	}
	
	for (i = 0; i <= n + 1; i++)
		for (j = 0; j <= m + 1; j++) b[i][j] = a[i][j];
	LeeRomeo();
	for (i = 0; i <= n + 1; i++)
		for (j = 0; j <= m + 1; j++) bb[i][j] = a[i][j];
	LeeJulieta();
//for(i=1;i<=n;i++){for(j=1;j<=m;j++) g<<setw(2)<<b[i][j]<<' ';g<<'\n';}g<<'\n';
//for(i=1;i<=n;i++){for(j=1;j<=m;j++) g<<setw(2)<<bb[i][j]<<' ';g<<'\n';}
	mini = 1000000;
	for (i = 1; i <= n; i++)
		for (j = 1; j <= m; j++)
			if (b[i][j] != -1 && b[i][j] != 0 && b[i][j] == bb[i][j] && b[i][j] < mini) {mini = b[i][j]; soli = i; solj = j;}
	g << mini << ' ' << soli << ' ' << solj << ' ' << '\n';
	f.close(); g.close();
	return 0;
}
n 0;
}