Pagini recente » Cod sursa (job #1593393) | Borderou de evaluare (job #1191036) | Cod sursa (job #335905) | Cod sursa (job #1254430) | Cod sursa (job #108137)
Cod sursa(job #108137)
#include <fstream>
using namespace std;
#define in "rj.in"
#define out "rj.out"
#define NMAX 101
#define INF 32001
const int di[] = { -1, -1, 0, 1, 1, 1, 0, -1 };
const int dj[] = { 0, 1, 1, 1, 0, -1, -1, -1 };
char a[NMAX][NMAX];
int n, m;
int ro[NMAX][NMAX];
int ju[NMAX][NMAX];
int ir, jr, ij, jj;
int iv, jv, pozi, pozj;
int q[NMAX*NMAX][2];
int prim, ultim;
int Ok1(int,int);
int Ok2(int,int);
void Lee1();
void Lee2();
int main()
{
ifstream fin ( in );
fin >> n >> m;
fin.get();
int i, j;
for ( i = 1; i <= n; ++i )
{
for ( j = 1; j <= m; ++j )
{
a[i][j] = fin.get();
if ( a[i][j] == 'R' ) { ir = i, jr = j; }
if ( a[i][j] == 'J' ) { ij = i, jj = j; }
ro[i][j] = ju[i][j] = INF;
}
fin.get();
}
while ( !fin.eof() ) fin.get();
fin.close();
Lee1();
Lee2();
ofstream fout ( out );
int minim = INF;
pozi = pozj = NMAX;
for ( i = 1; i <= n; ++i )
{
for ( j = 1; j <= m; ++j )
{
if ( ro[i][j] == ju[i][j] )
{
if ( ro[i][j] < minim )
{
minim = ro[i][j] + 1;
pozi = i;
pozj = j;
}
if ( ro[i][j] == minim )
{
if ( i < pozi )
{
pozi = i;
pozj = j;
}
if ( i == pozi && j < pozj )
{
pozi = i;
pozj = j;
}
}
}
}
}
fout << minim << " " << pozi << " " << pozj;// << "\n";
fout.close();
return 0;
}
void Lee1()
{
ro[ir][jr] = 0;
prim = ultim = 0;
q[prim][0] = ir;
q[prim][1] = jr;
int i, j, d;
while ( prim <= ultim )
{
for ( d = 0; d < 8; ++d )
{
i = q[prim][0];
j = q[prim][1];
iv = i + di[d];
jv = j + dj[d];
if ( Ok1(iv,jv) )
{
if ( ro[iv][jv] > ro[i][j] + 1 )
{
ro[iv][jv] = ro[i][j] + 1;
ultim++;
q[ultim][0] = iv;
q[ultim][1] = jv;
}
}
}
prim++;
}
}
void Lee2()
{
ju[ij][jj] = 0;
prim = ultim = 0;
q[prim][0] = ij;
q[prim][1] = jj;
int i, j, d;
while ( prim <= ultim )
{
for ( d = 0; d < 8; ++d )
{
i = q[prim][0];
j = q[prim][1];
iv = i + di[d];
jv = j + dj[d];
if ( Ok2(iv,jv) )
{
if ( ju[iv][jv] > ju[i][j] + 1 )
{
ju[iv][jv] = ju[i][j] + 1;
ultim++;
q[ultim][0] = iv;
q[ultim][1] = jv;
}
}
}
prim++;
}
}
int Ok1( int i, int j )
{
if ( i < 1 || i > n || j < 1 || j > m ) return 0;
if ( a[i][j] == 'X' ) return 0;
if ( ro[i][j] < INF ) return 0;
return 1;
}
int Ok2( int i, int j )
{
if ( i < 1 || i > n || j < 1 || j > m ) return 0;
if ( a[i][j] == 'X' ) return 0;
if ( ju[i][j] < INF ) return 0;
return 1;
}