Pagini recente » Autentificare | Arbori de intervale si aplicatii in geometria computationala | Cod sursa (job #168743) | Cod sursa (job #1294640) | Cod sursa (job #2017312)
#include <bits/stdc++.h>
using namespace std;
int n, m;
int rx, ry, jx, jy;
int dmin, fx, fy;
int romeo[102][102], julieta[102][102];
char aux[102];
int dx[8] = {-1, -1, 0, 1, 1, 1, 0, -1};
int dy[8] = { 0, 1, 1, 1, 0, -1, -1, -1};
bool OK( int x, int y, int arr[][102] ){
if( x < 0 || y < 0 || x >= n || y >= m )
return false;
if( arr[x][y] != 0 )
return false;
return true;
}
void lee( int sx, int sy, int arr[][102] ){
queue< pair<int, int> > coada;
coada.push( make_pair(sx, sy) );
arr[sx][sy] = 1;
int x, y, x_next, y_next;
while( !coada.empty() ){
x = coada.front().first;
y = coada.front().second;
coada.pop();
for(int d = 0; d < 8; d++){
x_next = x + dx[d];
y_next = y + dy[d];
if( OK(x_next, y_next, arr) ){
arr[x_next][y_next] = arr[x][y] + 1;
coada.push( make_pair(x_next, y_next) );
}
}
}
}
int main()
{
ifstream in("rj.in");
ofstream out("rj.out");
in>>n>>m; in.get();
for(int i = 0; i < n; i++){
in.getline(aux, 101);
for(int j = 0; j < m; j++){
if( aux[j] == 'X' )
romeo[i][j] = ( julieta[i][j] = -1);
else if( aux[j] == 'R' ){
rx = i; ry = j;
}
else if( aux[j] == 'J' ){
jx = i; jy = j;
}
}
}
lee(rx, ry, romeo);
lee(jx, jy, julieta);
dmin = 1000000000;
for(int i = 0; i < n; i++){
for(int j = 0; j < m; j++){
if( romeo[i][j] > 0 && julieta[i][j] > 0 ){
if( romeo[i][j] == julieta[i][j] ){
if( dmin > romeo[i][j] ){
dmin = romeo[i][j] - 1;
fx = i + 1; fy = j + 1;
}
}
}
}
}
out<<fx<<" "<<fx<<" "<<dmin;
return 0;
}