Cod sursa(job #874773)

Utilizator dragos-giidragos ghinoiu dragos-gii Data 9 februarie 2013 12:06:47
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.36 kb
#include<iostream>
#include<cstdio>
#include<queue>
#include<vector>

using namespace std;

void printMat(vector<vector<int> > mat){

	for(int i=0; i<mat.size(); i++){
		for(int j=0; j<mat[i].size(); j++)
			printf("%+2d ", mat[i][j]);
		cout<<'\n';
	}

}

vector<vector<int> > read(pair<int, int> &R, pair<int, int> &J){

	int m, n;
	FILE *f=fopen("rj.in", "r");

	fscanf(f, "%d%d", &n, &m);

	vector<vector<int> > mat(n+2, vector<int> (m+2));

	for(int i=0; i<n+1; i++){
		mat[i][0]=-1;
		mat[i][m+1]=-1;
	}
	for(int i=0; i<m+2; i++){
		mat[0][i]=-1;
		mat[n+1][i]=-1;
	}

	char a;
	fscanf(f, "% c", &a);

	for(int i=1; i<=n; i++){
		for(int j=1; j<=m; j++){
			
			fscanf(f, "%c", &mat[i][j]);	
		
			if(mat[i][j]=='X')
				mat[i][j]=-1;
			else if(mat[i][j]==' ')
				mat[i][j]=0;
			else if(mat[i][j]=='R'){
				R.first=i;
				R.second=j;
				mat[i][j]=0;		
			}else if(mat[i][j]=='J'){
				J.first=i;
				J.second=j;
				mat[i][j]=0;
			}
		}
		fscanf(f, "%c", &a);
	}
		
	fclose(f);

	return mat;

}

vector<vector<int> > dynamic(vector<vector<int> > mat, pair<int, int> p){

	queue<int> x, y;

	mat[p.first][p.second]=1;
	y.push(p.first);
	x.push(p.second);

	while(!x.empty() && !y.empty()){

		if(mat[y.front()+1][x.front()]==0){
			mat[y.front()+1][x.front()]=mat[y.front()][x.front()]+1;
			y.push(y.front()+1);
			x.push(x.front());
		}

		if(mat[y.front()-1][x.front()]==0){
			mat[y.front()-1][x.front()]=mat[y.front()][x.front()]+1;
			y.push(y.front()-1);
			x.push(x.front());
		}

		if(mat[y.front()][x.front()+1]==0){
			mat[y.front()][x.front()+1]=mat[y.front()][x.front()]+1;
			y.push(y.front());
			x.push(x.front()+1);
		}

		if(mat[y.front()][x.front()-1]==0){
			mat[y.front()][x.front()-1]=mat[y.front()][x.front()]+1;
			y.push(y.front());
			x.push(x.front()-1);
		}


		if(mat[y.front()+1][x.front()+1]==0){
			mat[y.front()+1][x.front()+1]=mat[y.front()][x.front()]+1;
			y.push(y.front()+1);
			x.push(x.front()+1);
		}

		if(mat[y.front()+1][x.front()-1]==0){
			mat[y.front()+1][x.front()-1]=mat[y.front()][x.front()]+1;
			y.push(y.front()+1);
			x.push(x.front()-1);
		}

		if(mat[y.front()-1][x.front()+1]==0){
			mat[y.front()-1][x.front()+1]=mat[y.front()][x.front()]+1;
			y.push(y.front()-1);
			x.push(x.front()+1);
		}

		if(mat[y.front()-1][x.front()-1]==0){
			mat[y.front()-1][x.front()-1]=mat[y.front()][x.front()]+1;
			y.push(y.front()-1);
			x.push(x.front()-1);
		}

		x.pop();
		y.pop();

	}


//	printMat(mat);
//	cout<<'\n';

	return mat;
}

int compare(vector<vector<int> > rmat, vector<vector<int> > jmat, pair<int, int> &coord){

	int time=9999999;

	for(int i=0; i<rmat.size(); i++){
		for(int j=0; j<rmat[i].size(); j++){
			if(rmat[i][j]==jmat[i][j] && rmat[i][j]<time && rmat[i][j]>0){
				time=rmat[i][j];
				coord.first=i;
				coord.second=j;
			}
		}
	}


	return time;
}

void print(int time, pair<int, int> coord){

	FILE *g=fopen("rj.out", "w");

	fprintf(g, "%d %d %d", time, coord.first, coord.second);

//	fclose(g);

}

int main(){

	pair<int, int> R, J;

	vector<vector<int> > mat=read(R, J);

	vector<vector<int> > rmat=dynamic(mat, R);
	vector<vector<int> > jmat=dynamic(mat, J);

	pair<int, int> coord;

	int time=compare(rmat, jmat, coord);	

	print(time, coord);

	return 0;
}