Cod sursa(job #2699281)

Utilizator danielsociuSociu Daniel danielsociu Data 24 ianuarie 2021 07:31:36
Problema Rj Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.13 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, 0, -1, 1, 1, 1, -1, -1};
int dy[8] = {1, -1, 0, 0, -1, 1, 1, -1};
char orase[maxn][maxn];
int dist[maxn][maxn], ans;
PII R, J, pans;

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

int lee (PII P) {
    queue<PII> que;
    que.push(P);

    while (!que.empty()) {
        PII node = que.front();
        que.pop();
        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);
                if (newn == J) {
                    return dist[newn.st][newn.nd];
                }
            }
        }
    }
    return -1;
}

int main()
{
    cin.tie(0);
    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};
                dist[i][j] = 3;
            }
            if (orase[i][j] == 'J') {
                J = {i,j};
            }
        }
    }
    ans = lee(R);
    FOR (i, 1, n) {
        FOR (j, 1, m) {
            if (dist[i][j] == (ans + 3)/2) {
                pans = {i, j};
            }
        }
    }
    cout << ans / 2 << ' ' << pans.st << ' ' << pans.nd << '\n';
}