Cod sursa(job #2953293)

Utilizator TheGodFather2131Alexandru Miclea TheGodFather2131 Data 10 decembrie 2022 21:29:48
Problema Rj Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.22 kb
//ALEXANDRU MICLEA

#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,fma")
#pragma GCC optimize("unroll-loops")
#include <vector>
#include <algorithm>
#include <string>
#include <cstring>
#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>
#include <iostream>
#include <array>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<double, double> pdd;
typedef vector<ll> vll;
typedef vector<int> vi;
typedef vector<vector<int> > vvi;
typedef vector<vector<ll> > vvll;
typedef vector<vector<pll> > vvpll;
typedef vector<pll> vpll;
typedef vector<pii> vpii;
const ll MOD = 1e9 + 7;
double eps = 1e-6;
#define forn(i,e) for(ll i = 1; i <= e; i++)
#define for0n(i,e) for(ll i = 0; i < (e); i++)
#define forsn(i,s,e) for(ll i = s; i <= e; i++)
#define rforn(i,s) for(ll i = s; i >= 1; i--)
#define rfor0n(i,s) for(ll i = s - 1; i >= 0; i--)
#define rforsn(i,s,e) for(ll i = s; i >= e; i--)
#define ln "\n"
#define dbg(x) cout<<#x<<" = "<<x<<ln
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define llinf 2e18
#define iinf 1e9
#define fast_cin() ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)
#define all(x) (x).begin(), (x).end()
#define sz(x) ((ll)(x).size())

//VARIABLES

queue <pii> q;
int dx[8] = {1,1,0,-1,-1,-1,0,1};
int dy[8] = {0,1,1,1,0,-1,-1,-1};
int p[105][105];
int t[2][105][105];
int m, n;
pii R, J;

//FUNCTIONS

void lee(pii pers, int tip) {
    q.push(pers);
    t[tip][pers.first][pers.second] = 0;

    while (!q.empty()) {
        pii now = q.front();
        q.pop();

        for0n(i, 8) {
            int x = now.first + dx[i];
            int y = now.second + dy[i];

            if (x < 1 || y < 1 || x > n || y > m) continue;
            if (p[x][y]) continue;
            if (t[tip][x][y] <= t[tip][now.first][now.second] + 1) continue;

            t[tip][x][y] = t[tip][now.first][now.second] + 1;

            q.push({ x, y });
        }
    }
}



//MAIN
int main() {
    fast_cin();

#ifdef INFOARENA
    freopen("rj.in", "r", stdin);
    freopen("rj.out", "w", stdout);
#endif

    cin >> n >> m;
    string lin;
    getline(cin, lin);
    forn(i, n) {
        getline(cin, lin);
        for0n(j, m) {
            //char c; cin >> c;
            if (lin[j] == 'X') p[i][j + 1] = 1;
            if (lin[j] == 'R') R = {i, j + 1};
            if (lin[j] == 'J') J = {i, j + 1};
            t[0][i][j + 1] = 1e9;
            t[1][i][j + 1] = 1e9;
        }
    }

    lee(R, 0);
    lee(J, 1);

    pii ans;
    int MIN = 1e9;

    forn(i, n) {
        forn(j, m) {
            if (t[0][i][j] == t[1][i][j] && MIN > t[1][i][j]) {
                MIN = t[1][i][j];
                ans = { i, j };
            }
        }
    }
    cout << MIN+1 << ' ' << ans.first << ' ' << ans.second << '\n';
    

    return 0;
}