Pagini recente » Cod sursa (job #3180937) | Cod sursa (job #2204073) | Cod sursa (job #2302801) | Cod sursa (job #1134214) | Cod sursa (job #2721755)
#include <fstream>
#include <queue>
using namespace std;
ifstream in("rj.in");
ofstream out("rj.out");
int dl[] = {-1, 0, 0, 1, -1, -1, 1, 1};
int dc[] = {0, -1, 1, 0, -1, 1, -1, 1};
const int N = 102;
int distR[N][N],distJ[N][N],n,m;
bool obs[N][N];
struct pos{
int l,c;
}romeo,juliet;
queue <pos> q;
void lee(pos pers, int dist[N][N]){
dist[pers.l][pers.c] = 1;
q.push(pers);
while(!q.empty()){
pos root = q.front();
q.pop();
for(int i=0;i<8;++i)
{
int new_l = root.l + dl[i], new_c = root.c + dc[i];
if(!obs[new_l][new_c] && dist[new_l][new_c]==0)
{
dist[new_l][new_c] = dist[root.l][root.c] + 1 ;
q.push({new_l,new_c});
}
}
}
}
void bordare()
{
for(int i=0;i<=n+1;++i){
obs[i][0] = obs[i][m+1] = 1;
}
for(int i=0;i<=m+1;++i){
obs[0][i] = obs[n+1][i] = 1;
}
}
int main()
{
in>>n>>m;
in.ignore(1);
for(int i=0;i<n;++i)
{
char line[101];
in.getline(line,N);
for(int j=0;j<m;++j)
{
switch(line[j]){
case 'R':
{
romeo = {i+1,j+1};
break;
}
case 'J':
{
juliet = {i+1,j+1};
break;
}
case 'X':
{
obs[i+1][j+1] = 1;
}
}
}
}
bordare();
lee(romeo,distR);
lee(juliet,distJ);
int minDist = N*N,imeet,jmeet;
for(int i=1;i<=n;++i)
{
for(int j=1;j<=m;++j)
{
if(!obs[i][j] && distR[i][j]!=0 && distR[i][j] == distJ[i][j] && distJ[i][j]<minDist){
minDist = distJ[i][j];
imeet = i, jmeet = j;
}
}
}
out<<minDist<<' '<<imeet<<' '<<jmeet;
return 0;
}