Pagini recente » Cod sursa (job #2479421) | Cod sursa (job #591684) | Cod sursa (job #1888682) | Cod sursa (job #1961627) | Cod sursa (job #553432)
Cod sursa(job #553432)
#include<fstream>
#include<vector>
#include<string>
#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 };
int n, m;
int ir, jr, ij, jj;
int v;
queue<pair<int, int> > Q;
char G[101][101];
int j[101][101];
void Read();
void BF( int x, int y );
void Solve();
bool OK( int i, int j);
void Write();
int main()
{
Read();
Solve();
fin.close();
fout.close();
return 0;
}
void Read()
{
fin >> n >> m;
fin.get();
char aux[101];
for( int i = 0; i < n; ++i )
{
fin.getline( aux, 101, '\n' );
strcpy( G[i], aux);
}
for( int i = 0; i < n; i++ )
for( int j2 = 0; j2 < m; j2++ )
{
if( G[i][j2] == 'R' )
{
ir = i;
jr = j2;
G[i][j2] = 1;
}
if( G[i][j2] == 'J' )
{
ij = i;
jj = j2;
}
if( G[i][j2] == 'X' )
G[i][j2] = -1;
if( G[i][j2] == ' ' )
G[i][j2] = INF;
j[i][j2] = INF;
}
}
void Solve()
{
v = 1;
BF( ir, jr );
v = 2;
BF( ij, jj );
/*
for( int i = 0; i < n; i++ )
{
for( int j2 = 0; j2 < m; j2++ )
fout << j[i][j2] << ' ';
fout << '\n';
}
*/
Write();
}
void BF( int x, int y )
{
Q.push( make_pair( x, y ) );
if( v == 1 )
G[x][y] = '1';
else
j[x][y] = 1;
pair< int, int > p;
while( !Q.empty() )
{
p = Q.front();
for( int d = 0; d < 8; ++d )
{
int iv = p.first + di[d];
int jv = p.second + dj[d];
if( OK( iv, jv ) )
{
if( v == 1 && G[iv][jv] > G[ p.first ][ p.second ] + 1 )
{
G[iv][jv] = G[ p.first ][ p.second ] + 1;
Q.push( make_pair( iv, jv ) );
}
if( v != 1 && j[iv][jv] > j[ p.first ][ p.second ] )
{
j[iv][jv] = j[ p.first ][ p.second ] + 1;
Q.push( make_pair( iv, jv ) );
}
}
}
Q.pop();
}
}
bool OK( int i, int j )
{
if( i < 0 || i >= n || j < 0 || j >= m || G[i][j] == -1 )
return false;
return true;
}
void Write()
{
int i1, j1, minim = INF;
for( int i = 0; i < n; ++i )
for( int j2 = 0; j2 < m; ++j2 )
{
int l = j[i][j2];
int l1 = G[i][j2] - 48;
if( l == l1 && minim > j[i][j2] )
{
i1 = i;
j1 = j2;
minim = j[i][j2];
}
}
fout << minim << ' '<< i1+1 << ' ' << j1+1;
}