Pagini recente » Cod sursa (job #1374409) | Cod sursa (job #2713000) | Cod sursa (job #239929) | Cod sursa (job #418939) | Cod sursa (job #1576914)
#include <fstream>
#include <cstring>
#include <queue>
#define NM 105
using namespace std;
ifstream fin("rj.in");
ofstream fout("rj.out");
const int dl[9]={0, -1, -1, -1, 0, 0, 1, 1, 1};
const int dc[9]={0, -1, 0, 1, -1, 1, -1, 0, 1};
struct pozitie
{
int l;
int c;
};
pozitie poz, poz2;
int N, M, i, j, a;
int pasi[NM][NM];
int pasi2[NM][NM];
int l1, c1, l2, c2;
int lin, col, mn;
char s[NM];
queue<pozitie> q, q2;
int main()
{
fin >> N >> M;
fin.get();
for (i=1; i<=N; i++)
{
fin.get(s, NM);
fin.get();
for (j=0; j<M; j++)
{
if (s[j]=='R')
{
l1=i;
c1=j+1;
}
if (s[j]=='J')
{
l2=i;
c2=j+1;
}
if (s[j]=='X')
{
pasi[i][j+1]=-1;
pasi2[i][j+1]=-1;
}
}
}
for (i=0; i<=M+1; i++)
{
pasi[0][i]=-1;
pasi[N+1][i]=-1;
pasi2[0][i]=-1;
pasi2[N+1][i]=-1;
}
for (i=0; i<=N+1; i++)
{
pasi[i][0]=-1;
pasi[i][M+1]=-1;
pasi2[i][0]=-1;
pasi2[i][M+1]=-1;
}
poz.l=l1;
poz.c=c1;
q.push(poz);
pasi[l1][c1]=1;
while (q.empty()==false)
{
poz=q.front();
q.pop();
for (i=1; i<=8; i++)
{
poz2.l=poz.l+dl[i];
poz2.c=poz.c+dc[i];
if (pasi[poz2.l][poz2.c]>-1)
{
if (pasi[poz2.l][poz2.c]==0)
{
pasi[poz2.l][poz2.c]=pasi[poz.l][poz.c]+1;
q.push(poz2);
}
else
{
a=pasi[poz2.l][poz2.c];
pasi[poz2.l][poz2.c]=min(pasi[poz2.l][poz2.c], pasi[poz.l][poz.c]+1);
if (a>pasi[poz2.l][poz2.c])
q.push(poz2);
}
}
}
}
poz.l=l2;
poz.c=c2;
q2.push(poz);
pasi2[l2][c2]=1;
while (q2.empty()==false)
{
poz=q2.front();
q2.pop();
for (i=1; i<=8; i++)
{
poz2.l=poz.l+dl[i];
poz2.c=poz.c+dc[i];
if (pasi2[poz2.l][poz2.c]>-1)
{
if (pasi2[poz2.l][poz2.c]==0)
{
pasi2[poz2.l][poz2.c]=pasi2[poz.l][poz.c]+1;
q2.push(poz2);
}
else
{
a=pasi2[poz2.l][poz2.c];
pasi2[poz2.l][poz2.c]=min(pasi2[poz2.l][poz2.c], pasi2[poz.l][poz.c]+1);
if (a>pasi2[poz2.l][poz2.c])
q2.push(poz2);
}
}
}
}
mn=2000000000;
for (i=1; i<=N; i++)
{
for (j=1; j<=M; j++)
{
if (pasi[i][j]<mn && pasi[i][j]>0 && pasi[i][j]==pasi2[i][j] && pasi2[i][j]<mn && pasi2[i][j]>0)
{
mn=pasi[i][j];
lin=i;
col=j;
}
}
}
fout << mn << " " << lin << " " << col << '\n';
fin.close();
fout.close();
return 0;
}