Pagini recente » Cod sursa (job #394860) | Cod sursa (job #2063049) | Cod sursa (job #960845) | Cod sursa (job #2109282) | Cod sursa (job #1593154)
#include <fstream>
#include <iostream>
#include <queue>
using namespace std;
char a[101][105];
int b[101][101],c[101][101],n,m;
pair<int,int>Romeo,Julieta;
int di[]={ 0, 1, 0,-1, 1,-1, 1,-1};
int dj[]={ 1, 0,-1, 0, 1,-1,-1, 1};
struct{int i,j;}x;
int tmin=9999999;
int ok(int i,int j)
{
if(i<1 || i>n || j<1 || j>m)
return 0;
if(a[i][j]=='X')
return 0;
return 1;
}
void lee1()
{
queue<pair<int,int> >q;
q.push(make_pair(Romeo.first,Romeo.second));
int i,j,ni,nj;
while(!q.empty())
{
i=q.front().first;
j=q.front().second;
q.pop();
for(int d=0;d<8;d++)
{
ni=i+di[d];
nj=j+dj[d];
if(ok(ni,nj) && b[ni][nj]<1)
{
b[ni][nj]=b[i][j]+1;
q.push(make_pair(ni,nj));
}
}
}
}
void lee2()
{
queue<pair<int,int> >q;
q.push(make_pair(Julieta.first,Julieta.second));
int i,j,ni,nj;
while(!q.empty())
{
i=q.front().first;
j=q.front().second;
if(c[i][j]==b[i][j] && c[i][j]<tmin)
{
tmin=c[i][j];
x.i=i;
x.j=j;
}
else if(c[i][j]==b[i][j] && c[i][j]==tmin)
{
if(i<x.i)
{
x.i=i;
x.j=j;
}
else if(i==x.i)
{
if(j<x.j)
{
x.j=j;
x.i=i;
}
}
}
q.pop();
for(int d=0;d<8;d++)
{
ni=i+di[d];
nj=j+dj[d];
if(ok(ni,nj) && c[ni][nj]<1)
{
c[ni][nj]=c[i][j]+1;
q.push(make_pair(ni,nj));
}
}
}
}
int main()
{
ifstream fin("rj.in");
ofstream fout("rj.out");
fin>>n>>m;
fin.get();
for(int i=1;i<=n;i++)
{
fin.getline(a[i]+1,101,'\n');
for(int j=1;j<=m;j++)
{
//fin.get(a[i][j]);
if(a[i][j]=='R')
{
Romeo.first=i;
Romeo.second=j;
}
else if(a[i][j]=='J')
{
Julieta.first=i;
Julieta.second=j;
}
}
}
lee1();
lee2();
fout<<tmin+1<<' '<<x.i<<' '<<x.j;
fout.close();
return 0;
}