Pagini recente » Cod sursa (job #551963) | Cod sursa (job #2253427) | Cod sursa (job #485567) | Cod sursa (job #1841709) | Cod sursa (job #1890602)
#include <iostream>
#include <fstream>
#include <queue>
using namespace std;
ifstream fin("rj.in");
ofstream fout("rj.out");
const int Nmax=100+5;
const int Di[]={-1,-1,-1,0,0,1,1,1};
const int Dj[]={-1,0,1,-1,1,-1,0,1};
const int INF=32000;
int n,m,minim,s1,s2,s3,s4,soli,solj;
queue<pair<short,short> >Q;
bool a[Nmax][Nmax];
short DPR[Nmax][Nmax],DPJ[Nmax][Nmax];
string s;
bool ok(int i,int j)
{
return i>=1 && i<=n && j<=m && j>=1;
}
void BF(short DP[Nmax][Nmax])
{
int i,j;
while(!Q.empty()){
i=Q.front().first;
j=Q.front().second;
Q.pop();
for(int d=0,ii,jj;d<9;++d)
{
ii=i+Di[d];
jj=j+Dj[d];
if(ok(ii,jj) && DP[ii][jj]>DP[i][j]+1 && a[ii][jj]==0)
{
DP[ii][jj]=DP[i][j]+1;
Q.push({ii,jj});
}
}
}
}
int main()
{
fin>>n>>m;
fin.get();
for(int i=1;i<=n;++i)
{
getline(fin,s);
//fout<<s<<'\n';
for(int j=1;j<=m;++j)
{
DPR[i][j]=INF;
DPJ[i][j]=INF;
if(s[j-1]==' ' or s[j-1]=='\0')a[i][j]=0;
else if(s[j-1]=='R'){s1=i;s2=j;a[i][j]=0;}
else if(s[j-1]=='J'){s3=i;s4=j;a[i][j]=0;}
else a[i][j]=1;
}
}
DPR[s1][s2]=1;
Q.push({s1,s2});BF(DPR);
DPJ[s3][s4]=1;
Q.push({s3,s4});BF(DPJ);
minim=INF;
for(int i=1;i<=n;++i)
for(int j=1;j<=m;++j)
if(DPJ[i][j]==DPR[i][j] && DPJ[i][j]<minim)
{
minim=DPR[i][j];
soli=i;
solj=j;
}
fout<<minim<<" "<<soli<<" "<<solj;
return 0;
}