Pagini recente » Cod sursa (job #665101) | Cod sursa (job #2666037) | Cod sursa (job #2349318) | Cod sursa (job #2379913) | Cod sursa (job #1124478)
#include <fstream>
#include <queue>
using namespace std;
ifstream fin ("rj.in");
ofstream fout ("rj.out");
const int INF = 0x3f3f3f3f;
const int di[8] = {-1, -1, 0, 1, 1, 1, 0, -1},
dj[8] = { 0, 1, 1, 1, 0,-1,-1, -1};
int m, n, iM, jM;
int a[102][102];
int b[102][102];
char t[102][102], x;
struct Cel{
int i, j;
} R, J;
queue<pair<int, int> > Q;
void Read();
void LeeR();
void LeeJ();
bool Ok(int i, int j);
void Solve();
int main()
{
Read();
LeeR();
LeeJ();
Solve();
return 0;
}
void Solve()
{
int mi = INF;
for ( int i = 1; i <= n; ++i )
for ( int j = 1; j <= m; ++j )
{
if (a[i][j] == b[i][j] && a[i][j] != 0 && a[i][j] < mi)
iM = i, jM = j, mi = a[i][j];
}
fout << mi << ' ' << iM << ' ' << jM;
}
void LeeJ()
{
int i, j, iv, jv;
b[J.i][J.j] = 1;
Q.push(make_pair(J.i, J.j));
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) && b[iv][jv] < 1 )
b[iv][jv] = b[i][j] + 1, Q.push(make_pair(iv, jv));
}
}
}
void LeeR()
{
int i, j, iv, jv;
a[R.i][R.j] = 1;
Q.push(make_pair(R.i, R.j));
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) && a[iv][jv] < 1 )
a[iv][jv] = a[i][j] + 1, Q.push(make_pair(iv, jv));
}
}
}
bool Ok(int i, int j)
{
if (i < 1 || j < 1 || i > n || j > m)
return false;
if (t[i][j] == 'X')
return false;
return true;
}
void Read()
{
fin >> n >> m;
for ( int i = 1; i <= n; ++i )
for ( int j = 1; j <= m; ++j )
{
x = fin.get();
if (x == '\n') x = fin.get();
if (x == 'X' || x == 'R' || x == 'J' || x == ' ')
t[i][j] = x;
if (x == 'R') R.i = i, R.j = j;
if (x == 'J') J.i = i, J.j = j;
}
}