Pagini recente » Cod sursa (job #318245) | Cod sursa (job #1148154) | Cod sursa (job #618681) | Cod sursa (job #3283659) | Cod sursa (job #2194604)
#include <iostream>
#include <fstream>
#include <algorithm>
#include <cstring>
#include <queue>
using namespace std;
ifstream fin("rj.in");
ofstream fout("rj.out");
//#define fin cin
//#define fout cout
int n, m;
int R[102][102], J[102][102];
bool harta[102][102];
bool in( pair<int, int> a ){
if( a.first >= 1 && a.first <= n && a.second >= 1 && a.second <= m ) return true;
else return false;
}
int main(){
int i1, j1, i2, j2;
int di[] = { -1, 0, 1, 0, -1, 1, 1, -1}, dj[] = { 0, 1, 0, -1, 1, 1, -1, -1};
queue<pair<int,int>> q;
fin >> n >> m;
string c;
getline(fin, c);
for( int i = 1 ; i <= n ; ++i ){
string s;
getline(fin, s);
for( int j = 0 ; j < m ; ++j ){
if( s[j] == 'X' ) harta[i][j+1] = 1;
else harta[i][j+1] = 0;
if( s[j] == 'R' ){
i1 = i;
j1 = j + 1;
}else if( s[j] == 'J' ){
i2 = i;
j2 = j + 1;
}
}
}
pair<int, int> crr, nou;
//R
R[i1][j1] = 1;
q.push(make_pair(i1, j1));
while( !q.empty() ){
crr = q.front();
q.pop();
for( int i = 0 ; i < 8 ; ++i ){
nou.first = crr.first + di[i];
nou.second = crr.second + dj[i];
if( in(nou) && !harta[nou.first][nou.second] && !R[nou.first][nou.second] ){
R[nou.first][nou.second] = R[crr.first][crr.second] + 1;
q.push(nou);
}
}
}
//J
J[i2][j2] = 1;
q.push(make_pair(i2, j2));
while( !q.empty() ){
crr = q.front();
q.pop();
for( int i = 0 ; i < 8 ; ++i ){
nou.first = crr.first + di[i];
nou.second = crr.second + dj[i];
if( in(nou) && !harta[nou.first][nou.second] && !J[nou.first][nou.second] ){
J[nou.first][nou.second] = J[crr.first][crr.second] + 1;
q.push(nou);
}
}
}
int minn = 10000;
for( int i = 1 ; i <= n ; ++i ){
for( int j = 1 ; j <= m ; ++j ){
if( R[i][j] && J[i][j] && R[i][j] == J[i][j] && R[i][j] < minn ){
minn = R[i][j];
crr = make_pair(i, j);
}
}
}
fout << minn << " " << crr.first << " " << crr.second;
return 0;
}