Pagini recente » Cod sursa (job #563723) | Cod sursa (job #2357958) | Cod sursa (job #2852750) | Cod sursa (job #1836521) | Cod sursa (job #1837065)
#include <fstream>
#include<queue>
using namespace std;
ifstream f("rj.in");
ofstream g("rj.out");
#define dmax 101
int n,m;
char a[dmax][dmax];
short romeo[dmax][dmax],julieta[dmax][dmax];
int start_r,stop_r,start_j,stop_j;
int x[]={0,-1,-1,0,1,1,1,0,-1},y[]={0,0,1,1,1,0,-1,-1,-1};
void Read()
{
f>>n>>m;
f.get();
for(int i=1; i<=n; i++)
{
f.getline(a[i],101);
for(int j=0; j<m; j++)
{
if(a[i][j]=='R')
{
romeo[i][j+1]=1;
start_r=i;
stop_r=j+1;
}
if(a[i][j]=='J')
{
julieta[i][j+1]=1;
start_j=i;
stop_j=j+1;
}
if(a[i][j]=='X') romeo[i][j+1]=julieta[i][j+1]=-1;
}
}
}
void Border()
{
for (int i=0; i<=n+1; i++)
romeo[i][0]=romeo[i][m+1]=-1;
for (int i=0; i<=m+1; i++)
romeo[0][i]=romeo[n+1][i]=-1;
for (int i=0; i<=n+1; i++)
julieta[i][0]=julieta[i][m+1]=-1;
for (int i=0; i<=m+1; i++)
julieta[0][i]=julieta[n+1][i]=-1;
}
void Lee_Romeo()
{
int i,j;
queue < pair <int , int> > coada;
coada.push(make_pair(start_r,stop_r));
while(!coada.empty())
{
i=coada.front().first;
j=coada.front().second;
coada.pop();
for(int k=1;k<=8;k++)
{
if(romeo[i+x[k]][j+y[k]]==0)
{
romeo[i+x[k]][j+y[k]]=romeo[i][j]+1;
coada.push(make_pair(i+x[k],j+y[k]));
}
}
}
}
void Lee_Julieta()
{
int i,j;
queue < pair <int , int> > coada;
coada.push(make_pair(start_j,stop_j));
while(!coada.empty())
{
i=coada.front().first;
j=coada.front().second;
coada.pop();
for(int k=1;k<=8;k++)
{
if(julieta[i+x[k]][j+y[k]]==0)
{
julieta[i+x[k]][j+y[k]]=julieta[i][j]+1;
coada.push(make_pair(i+x[k],j+y[k]));
}
}
}
}
void Find()
{
int minim=1001,ox,oy;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
if(romeo[i][j]==julieta[i][j] and romeo[i][j]>1)
{
if(romeo[i][j]<minim)
{
minim=romeo[i][j];
ox=i;
oy=j;
}
}
g<<minim<<" "<<ox<<" "<<oy;
}
int main()
{
Read();
Border();
Lee_Romeo();
Lee_Julieta();
Find();
return 0;
}