Pagini recente » Cod sursa (job #3293063) | Cod sursa (job #2138423) | Cod sursa (job #536133) | Cod sursa (job #703815) | Cod sursa (job #107994)
Cod sursa(job #107994)
#include <fstream>
using namespace std;
#define in "rj.in"
#define out "rj.out"
#define NMAX 101
#define INF 32000
char a[NMAX][NMAX];
typedef int MATR[NMAX][NMAX];
MATR mr;//matricea ROMEO
MATR mj;//matricea JULIETA
int c[NMAX*NMAX][2];
int n, m;
int prim, ultim;
int tmin;
int imin, jmin, iv, jv, is, js, ir, jr, ij, jj;
const int di[] = { -1, -1, 0, 1, 1, 1, 0, -1 };
const int dj[] = { 0, 1, 1, 1, 0, -1, -1, -1 };
void Read();
void LeeR();
void LeeJ();
void Write();
int Ok(int,int);
int Ok1(int,int);
void Write();
int main()
{
Read();
LeeR();
LeeJ();
Write();
return 0;
}
void Read()
{
ifstream fin("rj.in");
fin >> m >> n;
int i, j;
fin.get();
for ( i = 1; i <= m; i++ )
{
for ( j = 1; j <= n; j++ )
{
a[i][j] = fin.get();
if ( a[i][j] == 'R' ) ir = i, jr = j;
if ( a[i][j] == 'J' ) ij = i, jj = j;
mr[i][j] = mj[i][j] = INF;
}
fin.get(); // citeste Enter
}
for ( i = 0; i <= m + 1; i++)
mr[i][0] = mr[i][n+1] = mj[i][0] = mj[i][n+1] = INF;
for ( j = 0; j <= n + 1; j++)
mr[0][j] = mr[m+1][j] = mj[0][j] = mj[m+1][j] = INF;
mr[ir][jr] = 0;
mj[ij][jj] = 0;
fin.close();
}
void LeeR()
{
int i, j, d;
prim = ultim = 0;
c[prim][0] = ir;
c[prim][1] = jr;
mr[ir][jr] = 0;
while ( prim <= ultim )
{
for ( d = 0; d < 8; d++)
{
i = c[prim][0];
j = c[prim][1];
iv = i + di[d];
jv = j + dj[d];
if (Ok(iv,jv))
{
if ( mr[iv][jv] > mr[i][j] + 1)
{
mr[iv][jv] = mr[i][j] + 1;
ultim++;
c[ultim][0] = iv;
c[ultim][1] = jv;
}
}
}
prim++;
}
}
int Ok(int i, int j)
{
if ( i < 1 || i > m || j < 1 || j > n) return 0;
if ( a[i][j] == 'X') return 0;
if ( mr[i][j] < INF ) return 0;
return 1;
}
int Ok1(int i, int j)
{
if ( i < 1 || i > m || j < 1 || j > n) return 0;
if ( a[i][j] == 'X') return 0;
if ( mj[i][j] < INF ) return 0;
return 1;
}
void LeeJ()
{
int i, j, d;
prim = ultim = 0;
c[prim][0] = ij;
c[prim][1] = jj;
mj[ij][jj] = 0;
while ( prim <= ultim )
{
for ( d = 0; d < 8; d++)
{
i = c[prim][0];
j = c[prim][1];
iv = i + di[d];
jv = j + dj[d];
if ( Ok1(iv,jv))
{
if (mj[iv][jv] > mj[i][j] + 1)
{
mj[iv][jv] = mj[i][j] + 1;
ultim++;
c[ultim][0] = iv;
c[ultim][1] = jv;
}
}
}
prim++;
}
}
void Write()
{
ofstream fout ( out );
int i, j;
/*for ( i = 1; i <= m; i++)
{
for ( j = 1; j <= n; j++)
fout << mr[i][j] << " ";
fout << "\n";
}
fout << "\n";
for ( i = 1; i <= m; i++)
{
for ( j = 1; j <= n; j++)
fout << mj[i][j] << " ";
fout << "\n";
}
fout << "\n";
fout << ir << " " << jr << " " << ij << " " << jj << "\n";*/
tmin = INF;
for ( i = 1; i <= m; i++)
for ( j = 1; j <= n; j++)
if ( mr[i][j] == mj[i][j])
if ( mr[i][j] < tmin )
{
tmin = mr[i][j] + 1;
imin = i;
jmin = j;
}
fout << tmin << " " << imin << " " << jmin << "\n";
fout.close();
}