Cod sursa(job #2557970)

Utilizator furfur233Fur Fur furfur233 Data 26 februarie 2020 10:25:46
Problema Rj Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.04 kb
#include <bits/stdc++.h>

using namespace std;

ifstream fin("rj.in");
ofstream fout("rj.out");

long long n, m, mat[202][202];
char chr;

const long long addLin[]={-1,-1,-1,0,1,1,1,0};
const long long addCol[]={-1,0,1,1,1,0,-1,-1};

struct Pos{
	long long lin, col;
};
Pos r, j;

void scan(){
	fin>>n>>m;
	for(long long i=1; i<=n; i++){
		fin.get();
		for(long long jo=1; jo<=m; jo++){
			fin.get(chr);
			if(chr=='X'){
				mat[i][jo]=-1;
			}else if(chr==' '){
				mat[i][jo]=0;
			}else if(chr=='R'){
				mat[i][jo]=0;
				r.lin=i;
				r.col=jo;
			}else{
				mat[i][jo]=0;
				j.lin=i;
				j.col=jo;
			}
		}
	}
}

void border(){
	for(long long i=0; i<=n+1; i++){
		mat[i][0]=mat[i][n+1]=-1;
	}
	for(long long j=1; j<=n; j++){
		mat[0][j]=mat[n+1][j]=-1;
	}
}
queue<Pos> q, s;
Pos rasp;
Pos ngh, a,b;
void lee(){
	mat[r.lin][r.col]=mat[j.lin][j.col]=1;
	q.push(r);
	s.push(j);
	while(!q.empty() && !s.empty() && rasp.lin==0 && rasp.col==0){
		long long marime=q.size();
		for(long long t=0; t<marime; t++){
			a=q.front();
			q.pop();
			for(long long i=0; i<8; i++){
				ngh.lin=a.lin+addLin[i];
				ngh.col=a.col+addCol[i];
				if(mat[ngh.lin][ngh.col]==0){
					mat[ngh.lin][ngh.col]=mat[a.lin][a.col]+1;
					q.push(ngh);
				}
			}
		}
		marime=s.size();
		for(long long y=0; y<marime; y++){
			b=s.front();
			s.pop();
			for(long long i=0; i<8; i++){
				ngh.lin=b.lin+addLin[i];
				ngh.col=b.col+addCol[i];
				if(mat[ngh.lin][ngh.col]==0){
					mat[ngh.lin][ngh.col]=mat[b.lin][b.col]+1;
					s.push(ngh);
				}else if(mat[ngh.lin][ngh.col]==mat[a.lin][a.col]+1){
					rasp=ngh;
					break;
				}
			}
		}
	}
	fout<<mat[rasp.lin][rasp.col]<<" ";
}
queue<Pos> vf;
Pos mi;
void minim(){
	for(long long i=1; i<=rasp.lin; i++){
		for(long long j=1; j<=rasp.col; j++){
			if(mat[i][j]==mat[rasp.lin][rasp.col]){
				mi.lin=i;
				mi.col=j;
				vf.push(mi);
			}
		}
	}
	fout<<vf.front().lin<<" "<<vf.front().col;
}

int main(){
	scan();
	border();
	lee();
	minim();
}