Pagini recente » Cod sursa (job #1082234) | Cod sursa (job #3209391) | Cod sursa (job #2519387) | Cod sursa (job #633591) | Cod sursa (job #2371351)
#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;
}