Cod sursa(job #2699302)

Utilizator danielsociuSociu Daniel danielsociu Data 24 ianuarie 2021 08:42:54
Problema Rj Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.58 kb
#include <bits/stdc++.h>
using namespace std;
#define st          first
#define nd          second
#define pb          push_back
#define mkp         make_pair
#define lwbnd		lower_bound
#define upbnd		upper_bound
#define FOR(i,a,b)  for(int i=(a);i<=(b);++i)
#define FORS(i,a,b) for(int i=(a);i<(b);++i)
#define ALL(x)      x.begin(),x.end()
#define SZ(x)       ((int)(x).size())
#define MOD         1000000007 //998244353
#define maxn        105
typedef long long ll;
typedef pair<int,int> PII;
typedef vector<int> VI;
typedef vector<PII> VPII;
const int INF=0x3f3f3f3f;

int n,m;
int dx[8] = {0, 1, -1, 1, -1, 1, -1, 0};
int dy[8] = {-1, -1, -1, 0, 0, 1, 1, 1};
char orase[maxn][maxn];
int rr[maxn][maxn], jj[maxn][maxn], slashff;
PII R, J, pans;

bool valid(PII node) {
    return orase[node.st][node.nd] != 'X';
}

int lee (PII P, int dist[][maxn]) {
    queue<PII> que;
    que.push(P);

    while (!que.empty()) {
        PII node = que.front();
        que.pop();
        if (node == (PII){(P.st ^ J.st ^ R.st), (P.nd ^ J.nd ^ R.nd)}) {
            return dist[node.st][node.nd];
        }
        FOR (i, 0, 7) {
            PII newn = {node.st + dx[i], node.nd + dy[i]};
            if (valid(newn) && !dist[newn.st][newn.nd]) {
                dist[newn.st][newn.nd] = dist[node.st][node.nd] + 1;
                que.push(newn);
            }
        }
    }
    return -1;
}

int main()
{
    cin.tie(0); // OMG THEY HAVE TO SYNC KEKW
    ios_base::sync_with_stdio(0);
    freopen("rj.in","r",stdin);
    freopen("rj.out","w",stdout);
    cin >> n >> m >> ws;

    FOR (i, 1, n) {
        cin.getline(orase[i] + 1, m + 1);
    }
    FOR (i, 0 , n + 1) {
        orase[i][0] = orase[i][m + 1] = 'X';
    }
    FOR (i, 0, m + 1) {
        orase[0][i] = orase[n+1][i] = 'X';
    }
    FOR (i, 1, n) {
        FOR (j, 1, m) {
            if (orase[i][j] == 'R') {
                R = {i,j};
                rr[i][j] = 1;
            }
            if (orase[i][j] == 'J') {
                J = {i,j};
                jj[i][j] = 1;
            }
        }
    }
    if (R == J ) {
        cout << 0 << R.st << R.nd;
        return 0;
    }
    lee(R, rr);
    lee(J, jj);
    slashff = 105;
    FOR (i, 1, n) {
        FOR (j, 1, m) {
            if (jj[i][j] != 0 && jj[i][j] == rr[i][j]){ 
                if (jj[i][j] < slashff) {
                    pans = {i, j};
                    slashff = min(slashff, jj[i][j]);
                } else if (jj[i][j] == slashff && j < pans.nd) {
                    pans = {i,j};
                }
            }
        }
    }
    cout << slashff << ' ' << pans.st << ' ' << pans.nd << '\n';
}