Pagini recente » Cod sursa (job #1103616) | Cod sursa (job #1151916) | Borderou de evaluare (job #703670) | Cod sursa (job #2533930) | Cod sursa (job #2403306)
//ALEX ENACHE
#include <vector>
#include <algorithm>
#include <queue>
#include <map>
#include <set>
#include <unordered_map>
#include <time.h>
#include <iomanip>
#include <deque>
#include <math.h>
#include <cmath>
#include <assert.h>
#include <stack>
#include <bitset>
#include <random>
#include <chrono>
using namespace std;
//#include <iostream>
#include <fstream>
ifstream cin ("rj.in");ofstream cout ("rj.out");
int dx[] = {-1, -1, -1, 0, 0, 1, 1, 1} ;
int dy[] = {-1, 0, 1, -1, 1, -1, 0, 1} ;
bool copac[105][105];
int dist[2][105][105]; //tip , i , j
queue <pair < int , int > > q;
int n , m;
void solve (pair < int , int > sursa , int tip){
q.push(sursa);
dist[tip][sursa.first][sursa.second] = 0;
while (!q.empty()){
pair < int , int > now = q.front();
q.pop();
for (int i=0; i<8; i++){
int x = now.first + dx[i];
int y = now.second + dy[i];
if (x < 1 || y < 1 || x > n || y > m){
continue;
}
if (copac[x][y]){
continue;
}
if (dist[tip][x][y] <= dist[tip][now.first][now.second] + 1){
continue;
}
dist[tip][x][y] = dist[tip][now.first][now.second] + 1;
q.push({x , y});
}
}
}
int main() {
//freopen("input", "r", stdin);freopen("output", "w", stdout);
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cout << setprecision(10) << fixed;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
srand(time(NULL));
cin>>n>>m;
string s;
getline(cin , s);
pair < int , int > J , R;
for (int i=1; i<=n; i++){
getline(cin , s);
for (int j=0; j<m; j++){
if (s[j] == 'R'){
R = {i , j+1};
}
if (s[j] == 'J'){
J = {i , j+1};
}
if (s[j] == 'X'){
copac[i][j+1] = true;
}
dist[0][i][j+1] = 1e9;
dist[1][i][j+1] = 1e9;
}
}
solve (J , 0);
solve (R , 1);
int MIN = 1e9;
pair <int , int> ans;
for (int i=1; i<=n; i++){
for (int j=1; j<=m; j++){
if (dist[0][i][j] == dist[1][i][j] && (MIN > dist[0][i][j] || (MIN == dist[0][i][j] && j < ans.second))){
MIN = dist[0][i][j];
ans = {i , j};
}
}
}
cout<<MIN+1<<" "<<ans.first<<" "<<ans.second<<'\n';
return 0;
}