Pagini recente » Cod sursa (job #2688193) | Cod sursa (job #2432182) | Cod sursa (job #2953810) | Cod sursa (job #2953813) | Cod sursa (job #2131935)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("rj.in");
ofstream fout("rj.out");
struct poz
{
int x,y;
};
poz r,l;
char a[102];
bool f[105][105];
int R[102][102],J[102][102];
int dx[8]={1,1,1,0,0,-1,-1,-1};
int dy[8]={1,-1,0,1,-1,1,-1,0};
int n,m,i,j,k,p,c;
queue<poz>q1,q2;
int ok(int p1,int p2)
{
return(p1>0 && p2>0 && p1<=n && p2<=m);
}
void raspuns()
{int mx=INT_MAX;
for(i=1;i<=n;i++){
for(j=1;j<=m;j++){
if(R[i][j]>0 && J[i][j]>0){
R[i][j]=max(R[i][j],J[i][j]);
if(R[i][j]<mx && R[i][j]>0){
mx=R[i][j];
r.x=i;
r.y=j;
}
}}
}
fout<<mx<<" "<<r.x<<" "<<r.y;
}
void julieta()
{q2.push({l.x,l.y});
f[l.x][l.y]=1;
while(!q2.empty()){
int ii=q2.front().x;
int jj=q2.front().y;
if(ii==r.x && jj==r.y)
break;
q2.pop();
for(i=0;i<8;i++){
int ix=ii+dx[i];
int jy=jj+dy[i];
if(f[ix][jy]==0 && (J[ix][jy]==0 || J[ii][jj]+1<R[ix][jy])&& ok(ix,jy)){
q2.push({ix,jy});
J[ix][jy]=J[ii][jj]+1;
}}}
}
void romeo()
{q1.push({r.x,r.y});
f[r.x][r.y]=1;
while(!q1.empty()){
int ii=q1.front().x;
int jj=q1.front().y;
if(ii==l.x && jj==l.y)
break;
q1.pop();
for(i=0;i<8;i++){
int ix=ii+dx[i];
int jy=jj+dy[i];
if(f[ix][jy]==0 && (R[ix][jy]==0 || R[ii][jj]+1<R[ix][jy])&& ok(ix,jy)){
q1.push({ix,jy});
R[ix][jy]=R[ii][jj]+1;
}}}
}
void cetire()
{
fin>>n>>m;
fin.get();
for(i=1;i<=n;i++){
fin.get(a,102);
fin.get();
for(j=1;j<=m;j++){
if(a[j-1]=='R'){
r.x=i;
r.y=j;
continue;
}
if(a[j-1]=='J'){
l.x=i;
l.y=j;
continue;
}
if(a[j-1]=='X')
f[i][j]=1;
}
}
}
int main()
{cetire();
romeo();
julieta();
raspuns();
return 0;
}