Pagini recente » Cod sursa (job #2395089) | Cod sursa (job #1618044) | Cod sursa (job #391017) | Cod sursa (job #1326057) | Cod sursa (job #1330743)
#include <fstream>
#include <queue>
using namespace std;
ifstream fin("rj.in");
ofstream fout("rj.out");
const int DIM = 106, INF = 0x3f3f3f3f;
const int di[] = { -1, -1, -1, 0, 1, 1, 1, 0},
dj[] = { -1, 0, 1, 1, 1, 0, -1, -1};
int n, m, a[DIM][DIM];
int ipj, jpj, ipr, jpr;
int is, js, nrp;
char s[DIM];
int c[DIM][DIM], g[DIM][DIM];
queue<pair<int, int> > Q, Q1;
void Read();
void Julieta();
void Romeo();
bool OK(int i, int j);
int main()
{
Read();
Julieta();
Romeo();
nrp = INF;
for ( int i = 1; i <= n; i++ )
for ( int j = 1; j <= m; j++ )
if ( c[i][j] == g[i][j] && c[i][j] != INF && nrp > c[i][j] )
{
nrp = c[i][j];
is = i;
js = j;
}
fout << nrp << ' ' << is << ' ' << js;
fin.close();
fout.close();
return 0;
}
void Julieta()
{
int i, j, iv, jv;
while ( !Q.empty() )
{
i = Q.front().first;
j = Q.front().second;
Q.pop();
for ( int d = 0; d < 8; d++ )
{
iv = i + di[d];
jv = j + dj[d];
if ( OK(iv, jv) && c[iv][jv] > c[i][j] + 1 )
{
c[iv][jv] = c[i][j] + 1;
Q.push({iv, jv});
}
}
}
}
void Romeo()
{
int i, j, iv, jv;
while ( !Q1.empty() )
{
i = Q1.front().first;
j = Q1.front().second;
Q1.pop();
for ( int d = 0; d < 8; d++ )
{
iv = i + di[d];
jv = j + dj[d];
if ( OK(iv, jv) && g[iv][jv] > g[i][j] + 1 )
{
g[iv][jv] = g[i][j] + 1;
Q1.push({iv, jv});
}
}
}
}
bool OK(int i, int j)
{
if ( i < 1 || i > n || j < 1 || j > m ) return false;
if ( a[i][j] == 1 ) return false;
return true;
}
void Read()
{
fin >> n >> m;
fin.get();
for ( int i = 1; i <= n; i++ )
for ( int j = 1; j <= m; j++ )
{
c[i][j] = INF;
g[i][j] = INF;
}
for ( int i = 1; i <= n; i++ )
{
fin.getline(s, 106);
for ( int j = 1; j <= m; j++ )
{
if ( s[j - 1] == ' ' )
a[i][j] = 0;
else
if ( s[j - 1] == 'X' )
a[i][j] = 1;
else
if ( s[j - 1] == 'J' )
{
a[i][j] = 0;
c[i][j] = 1;
ipj = i, jpj = j;
Q.push({i, j});
}
else
if ( s[j - 1] == 'R' )
{
a[i][j] = 0;
g[i][j] = 1;
ipr = i, jpr = j;
Q1.push({i, j});
}
}
}
}