Pagini recente » Cod sursa (job #1178508) | Cod sursa (job #2720370) | Cod sursa (job #356042) | Cod sursa (job #524253) | Cod sursa (job #1392693)
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <queue>
using namespace std;
FILE *in =fopen("rj.in","r");
FILE *out=fopen("rj.out","w");
struct punct{int l,c;}romeo,julieta;
int dx[]={0,0,-1,1,-1,1,-1,1};
int dy[]={-1,1,0,0,-1,-1,1,1};
int const N=105;
int const MUT=8;
char matc[N][N];
int matr[N][N],matj[N][N];
bool gasitr,gasitj,viz[N][N];
int n,m;
void findc(int i, char c)
{
for(int j=0;j<m;j++)
if(matc[i][j]==c)
if(c=='R')
{
gasitr=true;
romeo.l=i;
romeo.c=j;
return;
}
else
{
gasitj=true;
julieta.l=i;
julieta.c=j;
return;
}
}
bool pot(punct x)
{
if(viz[x.l][x.c])
return false;
if((x.l<0)||(x.c<0))
return false;
if((x.l>=n)||(x.c>=m))
return false;
if(matc[x.l][x.c]=='X')
return false;
return true;
}
void init()
{
for(int i=0;i<n;i++)
for(int j=0;j<m;j++)
viz[i][j]=0;
}
void bfsromeo()
{
queue<punct> coada;
coada.push(romeo);
viz[romeo.l][romeo.c]=true;
punct curent;
punct next;
while(!coada.empty())
{
curent=coada.front();
coada.pop();
for(int i=0;i<MUT;i++)
{
next.l=curent.l+dy[i];
next.c=curent.c+dx[i];
if(!pot(next))
continue;
coada.push(next);
viz[next.l][next.c]=true;
matr[next.l][next.c]=matr[curent.l][curent.c]+1;
}
}
}
void bfsjulieta()
{
init();
queue<punct> coada;
coada.push(julieta);
viz[julieta.l][julieta.c]=true;
punct curent;
punct next;
while(!coada.empty())
{
curent=coada.front();
coada.pop();
for(int i=0;i<MUT;i++)
{
next.l=curent.l+dy[i];
next.c=curent.c+dx[i];
if(!pot(next))
continue;
coada.push(next);
viz[next.l][next.c]=true;
matj[next.l][next.c]=matj[curent.l][curent.c]+1;
}
}
}
void cauta()
{
for(int i=0;i<n;i++)
for(int j=0;j<m;j++)
if(matr[i][j]==matj[i][j])
{
fprintf(out,"%d %d %d",matr[i][j]+1,i+1,j+1);
return;
}
}
int main()
{
fscanf(in,"%d %d\n",&n,&m);
for(int i=0;i<n;i++)
{
fgets(matc[i],N,in);
if(!gasitr) findc(i,'R');
if(!gasitj) findc(i,'J');
}
bfsromeo();
bfsjulieta();
cauta();
return 0;
}