Pagini recente » Cod sursa (job #1776140) | Cod sursa (job #151221) | Cod sursa (job #961118) | Cod sursa (job #701917) | Cod sursa (job #2495662)
#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,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,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]=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(Inside(x,y) && a[x][y]!='X'&& dr[x][y]>dr[i][j]+1)
{
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]=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(Inside(x,y) && a[x][y]!='X' && dj[x][y]>dj[i][j]+1)
{
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]!=oo)
{
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;
}