Pagini recente » Cod sursa (job #509302) | Cod sursa (job #2879564) | Cod sursa (job #2285198) | Cod sursa (job #222600) | Cod sursa (job #553864)
Cod sursa(job #553864)
#include<fstream>
#include<queue>
using namespace std;
#define INF 0x3f3f3f3f
ifstream fin("rj.in");
ofstream fout("rj.out");
const int di[] = { -1, -1, 0, 1, 1, 1, 0, -1 },
dj[] = { 0, 1, 1, 1, 0, -1, -1, -1,};
queue<pair<int, int> > Q;
int n, m;
char g[120][120];
int r[120][120], j1[120][120];
int ir, jr, ij, jj;
void Read();
void Solve();
void Write();
int main()
{
Read();
Solve();
Write();
fin.close();
fout.close();
return 0;
}
void Read()
{
fin >> n >> m;
fin.get();
char aux[120];
for( int i = 0; i < n; ++i )
{
fin.getline( aux, 120, '\n' );
strcpy( g[i], aux );
}
for( int i = 0; i < n; ++i )
for( int j = 0; j < m; ++j )
{
if( g[i][j] == 'R' )
{
ir = i;
jr = j;
}
if( g[i][j] == 'J' )
{
ij = i;
jj = j;
}
r[i][j] = j1[i][j] = INF;
}
//fout << ir << ' '<< jr << ' ' << ij << ' ' << jj << ' ';
}
void Solve()
{
Q.push( make_pair( ir, jr ) );
r[ir][jr] = 1;
pair<int, int> k;
while( !Q.empty() )
{
k = Q.front();
for( int d = 0; d < 8; ++d )
{
int iv = k.first + di[d];
int jv = k.second + dj[d];
if( g[iv][jv] == ' ' && r[iv][jv] > r[ k.first ][ k.second ] + 1 )
{
r[iv][jv] = r[ k.first ][ k.second ] + 1;
Q.push( make_pair( iv, jv ) );
}
}
Q.pop();
}
Q.push( make_pair( ij, jj ) );
j1[ij][jj] = 1;
//pair<int, int> k;
while( !Q.empty() )
{
k = Q.front();
for( int d = 0; d < 8; ++d )
{
int iv = k.first + di[d];
int jv = k.second + dj[d];
if( g[iv][jv] == ' ' && j1[iv][jv] > j1[ k.first ][ k.second ] + 1 )
{
j1[iv][jv] = j1[ k.first ][ k.second ] + 1;
Q.push( make_pair( iv, jv ) );
}
}
Q.pop();
}
/*
for( int i = 0; i < n; ++i )
{
for( int j = 0; j < m; ++j )
fout << r[i][j] << ' ';
fout << '\n';
}
*/
}
void Write()
{
int x, y, mint = INF;
for( int i = 0; i < n; ++i )
for( int j = 0; j < m; ++j )
if( r[i][j] == j1[i][j] && mint > r[i][j] )
{
mint = r[i][j];
x = i;
y = j;
}
fout << mint << ' ' << x+1 << ' '<< y+1;
}