Pagini recente » Cod sursa (job #2337881) | Cod sursa (job #2592616) | Cod sursa (job #285477) | Cod sursa (job #2959313) | Cod sursa (job #433412)
Cod sursa(job #433412)
#include <fstream>
#include <queue>
#define INF 100000
using namespace std;
struct Cell {
int i;
int j;
}x;
queue<Cell> Q;
int b[101][101], r[101][101], ju[101][101];
long m, n, mini, minj;
long ipr, jpr, ipj, jpj;
long dmin = INF;
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 Write();
bool OK(int, int);
void Romeo();
void Julieta();
void Solve();
int main()
{
Read();
Romeo();
Julieta();
Solve();
Write();
return 0;
}
void Read()
{
ifstream fin("rj.in");
fin >> m >> n;
char linie[1000];
fin.get();
for ( int i = 0; i < m; i++)
{
fin.getline(linie, 101);
for ( int j = 0; j < n; j++)
{
if ( linie[j] == 'X')
b[i][j] = 1;
if ( linie[j] == ' ')
b[i][j] = 0;
if ( linie[j] == 'R')
{
ipr = i;
jpr = j;
}
if (linie[j] == 'J')
{
ipj = i;
jpj = j;
}
r[i][j] = INF;
ju[i][j] = INF;
}
}
fin.close();
}
void Romeo()
{
int i, j, k, iv, jv;
r[ipr][jpr] = 1;
x.i = ipr, x.j = jpr;
Q.push(x);
while ( !Q.empty() )
{
x = Q.front();
i = x.i;
j = x.j;
for ( k = 0; k < 8; k++)
{
iv = i + di[k];
jv = j + dj[k];
if ( OK(iv, jv) && r[iv][jv] > r[i][j] + 1)
{
r[iv][jv] = r[i][j] + 1;
x.i = iv;
x.j = jv;
Q.push(x);
}
}
Q.pop();
}
}
void Julieta()
{
//Q.clear();
int i, j, k, iv, jv;
ju[ipj][jpj] = 1;
x.i = ipj, x.j = jpj;
Q.push(x);
while ( !Q.empty() )
{
x = Q.front();
i = x.i;
j = x.j;
for ( k = 0; k < 8; k++)
{
iv = i + di[k];
jv = j + dj[k];
if ( OK(iv, jv) && ju[iv][jv] > ju[i][j] + 1)
{
ju[iv][jv] = ju[i][j] + 1;
x.i = iv;
x.j = jv;
Q.push(x);
}
}
Q.pop();
}
}
void Solve()
{
int i, j;
for ( i = 0; i < m; i++)
for ( j = 0; j < n; j++)
if ( r[i][j] == ju[i][j] && r[i][j] > 0)
{
if ( r[i][j] ==dmin)
{
if ( mini > i || mini == i && minj > j )
mini = i, minj = j;
}
if ( r[i][j] < dmin)
{
dmin = r[i][j];
mini = i + 1;
minj = j + 1;
}
}
}
bool OK(int i, int j)
{
return i >= 0 && i < n && j >= 0 && j < n && !b[i][j];
}
void Write()
{
ofstream fout("rj.out");
fout << dmin << ' ' << mini << ' ' << minj << '\n';
//fout << ipr << ' ' << jpr;
fout.close();
}