Cod sursa(job #2371351)

Utilizator _Victor_Victor Ciobanu _Victor_ Data 6 martie 2019 17:17:31
Problema Rj Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.74 kb
#include<bits/stdc++.h>
#define pii  pair <int,int>
#define F first 
#define S second
using namespace std;

int LJ[105][105],LR[105][105],n,m,rx,ry,jx,jy,s,X[8]={-1,0,1,-1,1,-1,0,1},Y[8]={-1,-1,-1,0,0,1,1,1};
string T[105];

bool val(int y,int x){
	return (x>0) && (y>0) && (x<=m) && (y<=n) && (T[y][x]!='X');
}

void write(int A[105][105]){
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			cout<<A[i][j]<<' ';
		}
		cout<<'\n';
	}
}

pii BFS(){
	queue <pii> R,J;
	//Initializam coada
	R.push({ry,rx});
	J.push({jy,jx});
	LJ[jy][jx]=LR[ry][rx]=1;
	pii cj=J.front(),cr=R.front();
	while(!LR[cj.F][cj.S] && !LJ[cr.F][cr.S]){
		if(LR[cr.F][cr.S]<=LJ[cj.F][cj.S]){
			for(int i=0;i<8;i++){
				if(!LR[cr.F+Y[i]][cr.S+X[i]] && val(cr.F+Y[i],cr.S+X[i])){
					R.push({cr.F+Y[i],cr.S+X[i]});
					LR[cr.F+Y[i]][cr.S+X[i]]=LR[cr.F][cr.S]+1;
				}
			}
			R.pop();
			cr=R.front();
		}
		if(LJ[cj.F][cj.S]<=LR[cr.F][cr.S]){
			for(int i=0;i<8;i++){
			if(!LJ[cj.F+Y[i]][cj.S+X[i]] && val(cj.F+Y[i],cj.S+X[i])){
					J.push({cj.F+Y[i],cj.S+X[i]});
					LJ[cj.F+Y[i]][cj.S+X[i]]=LJ[cj.F][cj.S]+1;
				}
			}
			J.pop();
			cj=J.front();
		}
		/*cout<<"ROMEO:\n";
		write(LR);
		cout<<"JULIETT:\n";
		write(LJ);
		cout<<'\n';*/
	}
	if(LR[cj.F][cj.S]){
		s=LR[cj.F][cj.S];
		return {cj.F,cj.S};
	}else{
		s=LJ[cr.F][cr.S];
		return {cr.F,cr.S};
	}
	return {0,0};
}

int main(){
	ifstream cin("rj.in");
	ofstream cout("rj.out");
	cin>>n>>m;
	getline(cin,T[0]);
	for(int i=1;i<=n;i++){
		getline(cin,T[i]);
		T[i]='&'+T[i];
		for(int j=1;j<=m;j++){
			if(T[i][j]=='R'){
				ry=i;
				rx=j;
			}else if(T[i][j]=='J'){
				jy=i;
				jx=j;
			}
		}
	}
	pii cs=BFS();
	cout<<s<<' '<<cs.F<<' '<<cs.S;
	return 0;
}