Pagini recente » Cod sursa (job #169188) | Cod sursa (job #572082) | Cod sursa (job #2888495) | Cod sursa (job #2264483) | Cod sursa (job #1751998)
#include <bits/stdc++.h>
#define oo 1000000
using namespace std;
ifstream fin("rj.in");
ofstream fout("rj.out");
int n,m,xr,yr,xj,yj,dr[105][105],dj[105][105];
char a[105][105];
int dx[]={0,0,-1,1,-1,1,-1,1};
int dy[]={-1,1,0,0,-1,1,1,-1};
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,105);
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;
}
}
}
void Bordare()
{
int i;
for (i=0;i<=m+1;i++) a[0][i]=a[n+1][i]='X';
for (i=0;i<=n+1;i++) a[i][0]=a[i][m+1]='X';
}
void Init()
{
int i,j;
for (i=1;i<=n;i++)
for (j=1;j<=m;j++)
dj[i][j]=dr[i][j]=oo;
}
void Lee_R()
{
int i,j,x,y,k;
q.push(make_pair(xr,yr));
dr[xr][yr]=1;
while(!q.empty())
{
i=q.front().first;
j=q.front().second;
q.pop();
for (k=0;k<8;k++)
{
x=i+dx[k];
y=j+dy[k];
if (dr[x][y]>dr[i][j]+1 && a[x][y]!='X')
{
dr[x][y]=dr[i][j]+1;
q.push(make_pair(x,y));
}
}
}
}
void Lee_J()
{
int i,j,x,y,k;
q.push(make_pair(xj,yj));
dj[xj][yj]=1;
while(!q.empty())
{
i=q.front().first;
j=q.front().second;
q.pop();
for (k=0;k<8;k++)
{
x=i+dx[k];
y=j+dy[k];
if (dj[x][y]>dj[i][j]+1 && a[x][y]!='X')
{
dj[x][y]=dj[i][j]+1;
q.push(make_pair(x,y));
}
}
}
}
void Intalnire()
{
int i,j,mini,poz1,poz2;
mini=oo;
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
if(dr[i][j]==dj[i][j] && mini>dr[i][j])
{
mini=dr[i][j];
poz1=i;
poz2=j;
}
fout<<mini<<" "<<poz1<<" "<<poz2<<"\n";
}
int main()
{
Citire();
Bordare();
Init();
Lee_R();
Lee_J();
Intalnire();
fin.close();
fout.close();
return 0;
}