Cod sursa(job #2024870)

Utilizator eilerGabriel-Ciprian Stanciu eiler Data 21 septembrie 2017 14:42:06
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.58 kb
#include <fstream>
#include <queue>
using namespace std;

struct punct {
	int x, y;
};

int N, M;
punct R, J;
bool tab[100][100];

int l[8]={-1, -1, -1, 0, 0, 1, 1, 1}, c[8]={-1, 0, 1, -1, 1, -1, 0, 1};

bool inBounds(int i, int j){
	return i>=0 && i<N && j>=0 && j<M;
}

void lee(punct S, int T[100][100]){
	queue<int> timp;
	queue<punct> poz;
	punct Q;
	int h, i, j, in, jn, t;

	T[S.x][S.y]=1;
	timp.push(1);
	poz.push(S);
	while (!timp.empty()){
		Q=poz.front();
		i=Q.x; j=Q.y;
		t=timp.front();

		for (h=0; h<8; h++){
			in=i+l[h]; jn=j+c[h];

			if (inBounds(in, jn) && tab[in][jn]==false && T[in][jn]>t+1){
				T[in][jn]=t+1;

				Q.x=in; Q.y=jn;
				timp.push(t+1);
				poz.push(Q);
			}
		}

		timp.pop(); poz.pop();
	}
}

int main(){
	int i, j;
	char c;

	ifstream fin ("rj.in");
	fin >> N >> M;
	for (i=0; i<N; i++){
		fin.get();
		for (j=0; j<M; j++){
			c=fin.get();
			if (c=='X')
				tab[i][j]=true;
			else if (c=='R'){
				R.x=i; R.y=j;
			}
			else if (c=='J'){
				J.x=i; J.y=j;
			}
		}
	}
	fin.close();

	int romeo[100][100], julieta[100][100];

	for (i=0; i<N; i++)
		for (j=0; j<M; j++)
			romeo[i][j]=julieta[i][j]=100*100+1;

	lee(R, romeo);
	lee(J, julieta);

	punct Min;
	int tMin;

	tMin=100*100+1;
	Min.x=0; Min.y=0;

	for (i=0; i<N; i++)
		for (j=0; j<M; j++)
	    if (romeo[i][j]==julieta[i][j] && romeo[i][j]<tMin){
				tMin=romeo[i][j];
				Min.x=i+1; Min.y=j+1;
	    }

	ofstream fout ("rj.out");
	fout << tMin << ' ' << Min.x << ' ' << Min.y << '\n';
	fout.close();

	return 0;
}