Pagini recente » Cod sursa (job #1603923) | Cod sursa (job #2023890) | Cod sursa (job #2136980) | Cod sursa (job #193832) | Cod sursa (job #498737)
Cod sursa(job #498737)
#include <algorithm>
#include <cassert>
#include <cctype>
#include <cmath>
#include <cstring>
#include <ctime>
#include <bitset>
#include <deque>
#include <fstream>
#include <list>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
using namespace std;
typedef bool int01;
typedef char cha08;
typedef short int int16;
typedef int int32;
typedef float rea32;
typedef long long int int64;
typedef double rea64;
const cha08 Input[] = "rj.in";
const cha08 Output[] = "rj.out";
const int32 Dim = 105;
const int32 Inf = 0x3f3f3f3f;
const int32 dx[] = {0, -1, -1, -1, 0, 1, 1, 1};
const int32 dy[] = {1, 1, 0, -1, -1, -1, 0, 1};
cha08 h[Dim][Dim];
int32 N, M, XXX, XX, YY, X[2], Y[2];
int32 d[2][Dim][Dim];
queue < pair <int32, int32> > q;
int01 OK( int32 x, int32 y, int32 k ) {
if( x < 1 || x > N )
return 0;
if( y < 1 || y > M )
return 0;
if( h[x][y] == 'X' )
return 0;
if( d[k][x][y] != -1 )
return 0;
return 1;
}
void BF( int32 k ) {
int32 i, x, y;
for( i = 1; i <= N; ++i )
memset( d[k][i], -1, sizeof( d[k][i] ) );
q.push( make_pair( X[k], Y[k] ) );
d[k][X[k]][Y[k]] = 0;
while( !q.empty() ) {
x = q.front().first;
y = q.front().second;
q.pop();
for( i = 0; i < 8; ++i )
if( OK( x + dx[i], y + dy[i], k ) ) {
d[k][x + dx[i]][y + dy[i]] = d[k][x][y] + 1;
q.push( make_pair( x + dx[i], y + dy[i] ) );
}
}
}
int32 main() {
ifstream fin( Input );
ofstream fout( Output );
int32 i, j;
fin >> N >> M;
fin.ignore( 1, '\n' );
for( i = 1; i <= N; ++i ) {
fin.getline( h[i] + 1, Dim );
for( j = 1; j <= M; ++j ) {
if( h[i][j] == 'R' ) {
X[0] = i;
Y[0] = j;
}
if( h[i][j] == 'J' ) {
X[1] = i;
Y[1] = j;
}
}
}
BF( 0 );
BF( 1 );
XXX = Inf;
for( i = 1; i <= N; ++i )
for( j = 1; j <= M; ++j )
if( d[0][i][j] != -1 && d[0][i][j] == d[1][i][j] && d[0][i][j] + 1 < XXX ) {
XXX = d[0][i][j] + 1;
XX = i;
YY = j;
}
fout << XXX << " " << XX << " " << YY;
fin.close();
fout.close();
return 0;
}