Pagini recente » Cod sursa (job #1880052) | Cod sursa (job #2849285) | Cod sursa (job #2669460) | Cod sursa (job #1848426) | Cod sursa (job #1329181)
#include <algorithm>
#include <fstream>
#include <deque>
using namespace std;
const int INF= ( 1<<30 ), NMAX= 100;
const int dx[] = {0, 1, 0, -1, -1, -1, 1, 1}, dy[] = {1, 0, -1, 0, -1, 1, 1, -1};
ifstream in( "rj.in" );
ofstream out( "rj.out" );
int R[NMAX+2][NMAX+2], J[NMAX+2][NMAX+2];
deque <int> qx, qy;
void ans( int N, int M )
{
int x, y, tmin= INF;
for( int i= 1; i<=N; ++i )
{
for( int j= 1; j<=M; ++j )
{
if( R[i][j] == J[i][j] && R[i][j] != -1 )
{
if( tmin > R[i][j] && R[i][j] != 0 )
{
tmin= R[i][j];
x= i;
y= j;
}
}
}
}
out << tmin << " " << x << " " << y;
}
void lee_R()
{
int x, y;
while( !qx.empty() )
{
x = qx.front();
y = qy.front();
qx.pop_front();
qy.pop_front();
for( int i= 0; i<8; ++i )
{
if( R[ x+dx[i] ][ y+dy[i] ] == 0 )
{
R[ x+dx[i] ][ y+dy[i] ] = R[x][y] + 1;
qx.push_back( x+dx[i] );
qy.push_back( y+dy[i] );
}
}
}
}
void lee_J()
{
int x, y;
while( !qx.empty() )
{
x = qx.front();
y = qy.front();
qx.pop_front();
qy.pop_front();
for( int i= 0; i<8; ++i )
{
if( J[ x + dx[i] ][ y + dy[i] ] == 0 )
{
J[ x + dx[i] ][ y + dy[i] ] = J[x][y] + 1;
qx.push_back( x + dx[i] );
qy.push_back( y + dy[i] );
}
}
}
}
int main()
{
int N, M, Rx, Ry, Jx, Jy;
char c;
in >> N >> M;
in.get(c);
for( int i= 1; i<=N; ++i )
{
for( int j= 1; j<=M+1; ++j )
{
in.get(c);
if( c == 'X' )
R[i][j] = J[i][j] = -1;
if( c == 'R' )
{
Rx = i;
Ry = j;
R[Rx][Ry] = 1;
}
if( c == 'J' )
{
Jx = i;
Jy = j;
J[Jx][Jy] = 1;
}
if( c == '\n' )
j = INF;
}
}
for(int i = 0; i <= M + 1; i++)
{
R[0][i] = R[N+1][i] = J[0][i] = J[N+1][i] = -1;
}
for(int i = 0; i <= N + 1; i++)
{
R[i][0] = R[i][M+1] = J[i][0] = J[i][M+1] = -1;
}
qx.push_back(Rx);
qy.push_back(Ry);
lee_R();
qx.push_back(Jx);
qy.push_back(Jy);
lee_J();
ans( N, M );
return 0;
}