Pagini recente » Cod sursa (job #187743) | Cod sursa (job #1463464) | Cod sursa (job #1589145) | Cod sursa (job #1229672) | Cod sursa (job #2494984)
#include <bits/stdc++.h>
#define oo 5555555
using namespace std;
ifstream fin("rj.in");
ofstream fout("rj.out");
int n,m,xr,yr,xj,yj;
char a[105][105];
int dr[105][105];
int dj[105][105];
int dx[]={0,0,-1,1};
int dy[]={-1,1,0,0};
queue<pair<int,int> > q;
void Citire()
{
int i,j;
fin>>n>>m;
fin.get();
for(i=1;i<=n;i++)
fin.getline(a[i]+1,103);
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
{
if(a[i][j]=='R') {xr=i;yr=j;}
else if(a[i][j]=='J') {xj=i;yj=j;}
}
}
bool Inside(int i,int j)
{
return (i>=1 && i<=n && j>=1 && j<=m);
}
void Lee(char P)
{
int i,j,x,y,k;
if(P=='R')
{
q.push({xr,yr});
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
dr[i][j]=oo;
dr[xr][yr]=0;
while(!q.empty())
{
i=q.front().first;
j=q.front().second;
q.pop();
for(k=0;k<4;k++)
{
x=i+dx[k];
y=j+dy[k];
if(Inside(x,y) && dr[x][y]>dr[i][j]+1 && a[i][j]!='X')
{
dr[x][y]=dr[i][j]+1;
q.push({x,y});
}
}
}
}
else
{
q.push({xj,yj});
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
dj[i][j]=oo;
dj[xj][yj]=0;
while(!q.empty())
{
i=q.front().first;
j=q.front().second;
q.pop();
for(k=0;k<4;k++)
{
x=i+dx[k];
y=j+dy[k];
if(Inside(x,y) && dj[x][y]>dj[i][j]+1 && a[i][j]!='X')
{
dj[x][y]=dj[i][j]+1;
q.push({x,y});
}
}
}
}
}
void Caut()
{
int i,j,tmin=1e9,x,y;
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
if(dr[i][j]==dj[i][j] && dr[i][j]!=0)
{
if(tmin>dr[i][j])
{
tmin=dr[i][j];
x=i;
y=j;
}
}
fout<<tmin<<" "<<x<<" "<<y<<"\n";
fout.close();
}
int main()
{
Citire();
Lee('R');
Lee('J');
Caut();
return 0;
}