Cod sursa(job #2558023)

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

using namespace std;

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

long long n, m, mat[102][102], jul[102][102];
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]=jul[i][jo]=-1;
			}else if(chr==' '){
				mat[i][jo]=jul[i][jo]=0;
			}else if(chr=='R'){
				mat[i][jo]=jul[i][jo]=0;
				r.lin=i;
				r.col=jo;
			}else{
				mat[i][jo]=jul[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;
		jul[i][0]=jul[i][n+1]=-1;
	}
	for(long long j=1; j<=n; j++){
		mat[0][j]=mat[n+1][j]=-1;
		jul[0][j]=jul[n+1][j]=-1;
	}
	
}
queue<Pos> q;
Pos ngh, a,b;
void lee(){
	mat[r.lin][r.col]=1;
	q.push(r);
	while(!q.empty()){
		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);
			}
		}
	}
	jul[j.lin][j.col]=1;
	q.push(j);
	while(!q.empty()){
		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(jul[ngh.lin][ngh.col]==0){
				jul[ngh.lin][ngh.col]=jul[a.lin][a.col]+1;
				q.push(ngh);
			}
		}
	}
}
Pos rasp[102*102], min;
long long in=0, val=99999;
void solutie(){
	for(int i=1; i<=n; i++){
		for(int j=1; j<=m; j++){
			if(mat[i][j]==jul[i][j] && mat[i][j]>0){
				rasp[in].lin=i;
				rasp[in].col=j;
				if(mat[i][j]<val){
					val=mat[i][j];
				}
				in++;
			}
		}
	}
	for(int h=0; h<in; h++){
		if(mat[rasp[h].lin][rasp[h].col]==val){
			fout<<val<<" "<<rasp[h].lin<<" "<<rasp[h].col;
			break;
		}
	}
}

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