Pagini recente » Cod sursa (job #1582196) | Cod sursa (job #1615778) | Cod sursa (job #805024) | Cod sursa (job #840907) | Cod sursa (job #1317234)
#include <fstream>
#include <queue>
using namespace std;
ifstream fin("rj.in");
ofstream fout("rj.out");
#define Dim 160
#define INF 0x3f3f3f3f
const int di[] = { -1, -1, -1, 0, 1, 1, 1, 0 };
const int dj[] = { -1, 0, 1, 1, 1, 0,-1,-1 };
queue<pair<int,int> >Q, Q1;
int n, m, ipoz = INF, jpoz = INF;
char s[165];
int c[Dim][Dim];
int a[Dim][Dim];
int d[Dim][Dim];
void Read();
void LeeRomeo();
void LeeJuli();
bool Ok(int i, int j);
int minim = INF, imin, jmin;
int main()
{
Read();
LeeRomeo();
LeeJuli();
for ( int i = 0; i < n; ++i )
for ( int j = 0; j < m; ++j )
if ( c[i][j] == d[i][j] && c[i][j] && a[i][j] == 1 )
if ( c[i][j] < minim )
{
minim = c[i][j];
imin = i + 1;
jmin = j + 1;
}
fout << minim << ' ' << imin << ' ' << jmin;
fin.close();
fout.close();
return 0;
}
void LeeJuli()
{
int i, j, iv, jv;
while ( !Q1.empty() )
{
i = Q1.front().first;
j = Q1.front().second;
Q1.pop();
for ( int p = 0; p < 8; ++p )
{
iv = i + di[p];
jv = j + dj[p];
if ( Ok( iv, jv ) && d[i][j] + 1 < d[iv][jv] )
{
d[iv][jv] = d[i][j] + 1;
Q1.push({ iv, jv });
}
}
}
}
void LeeRomeo()
{
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[i][j] + 1 < c[iv][jv] )
{
c[iv][jv] = c[i][j] + 1;
Q.push({ iv, jv });
}
}
}
}
bool Ok(int i, int j)
{
if ( i < 0 or i > n - 1 or j < 0 or j > m - 1 or a[i][j] == -1 )
return false;
return true;
}
void Read()
{
fin >> n >> m;
fin.get();
for ( int i = 0; i < n; ++i )
{
fin.getline( s, 150, '\n' );
for ( int j = 0; j < m; ++j )
{
if ( s[j] == ' ' )
a[i][j] = 1;
if ( s[j] == 'X' )
a[i][j] = -1;
c[i][j] = d[i][j] = INF;
if ( s[j] == 'R')
{
Q.push({i, j});
c[i][j] = 1;
}
if ( s[j] == 'J' )
{
Q1.push({i, j});
d[i][j] = 1;
}
}
}
}