Pagini recente » Cod sursa (job #1754112) | Cod sursa (job #804322) | Cod sursa (job #477486) | Cod sursa (job #2640396) | Cod sursa (job #1992922)
#include<fstream>
#include<iostream>
#include<cstring>
#include<queue>
using namespace std;
ifstream fin("rj.in");
ofstream fout("rj.out");
int n,m;
char x[105][105];
int a[105][105],b[105][105];
int ju[105][105],r[105][105],tmin=10005,el,ec,jl,jc,rl,rc;
queue<pair<int,int> >q;
int dl[8]={0,0,1,1,1,-1,-1,-1};
int dc[8]={1,-1,-1,0,1,-1,0,1};
void ve1()
{
int l,c,lnou,cnou;
while(!q.empty())
{
l=q.front().first;
c=q.front().second;
q.pop();
a[l][c]=0;
for(int i=0;i<8;i++)
{
lnou=l+dl[i];
cnou=c+dc[i];
if(lnou>0&&lnou<=n&&cnou>=0&&cnou<m&&x[lnou][cnou]==' ')
if(ju[l][c]+1<ju[lnou][cnou]||ju[lnou][cnou]==0)
{
ju[lnou][cnou]=ju[l][c]+1;
if(a[lnou][cnou]==0)
{
a[lnou][cnou]=1;
q.push(make_pair(lnou,cnou));
}
}
}
}
}
void ve2()
{
int l,c,lnou,cnou;
while(!q.empty())
{
l=q.front().first;
c=q.front().second;
q.pop();
b[l][c]=0;
for(int i=0;i<8;i++)
{
lnou=l+dl[i];
cnou=c+dc[i];
if(lnou>0&&lnou<=n&&cnou>=0&&cnou<m&&x[lnou][cnou]==' ')
if(r[l][c]+1<r[lnou][cnou]||r[lnou][cnou]==0)
{
r[lnou][cnou]=r[l][c]+1;
if(b[lnou][cnou]==0)
{
b[lnou][cnou]=1;
q.push(make_pair(lnou,cnou));
}
}
}
}
}
int main()
{
fin>>n>>m;
for(int i=0;i<=n;i++)
{
fin.getline(x[i],105);
if(strlen(x[i])!=m)
{
int t=strlen(x[i]);
for(int j=t;j<m;j++)
x[i][j]=' ';
x[i][m]='\0';
}
}
for(int i=1;i<=n;i++)
for(int j=0;j<m;j++)
if(x[i][j]=='J')
{
jl=i;
jc=j;
}
else
if(x[i][j]=='R')
{
rl=i;
rc=j;
}
a[jl][jc]=1;
ju[jl][jc]=1;
q.push(make_pair(jl,jc));
ve1();
b[rl][rc]=1;
r[rl][rc]=1;
q.push(make_pair(rl,rc));
ve2();
for(int i=1;i<=n;i++)
for(int j=0;j<m;j++)
if(x[i][j]==' '&&r[i][j]==ju[i][j]&&r[i][j]<tmin&&r[i][j])
{
tmin=r[i][j];
el=i;
ec=j+1;
}
fout<<tmin<<' '<<el<<' '<<ec;
}