Cod sursa(job #2702291)

Utilizator As932Stanciu Andreea As932 Data 3 februarie 2021 16:44:14
Problema Rj Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.94 kb
#include <fstream>
#include <queue>
#define per pair<int,int>

using namespace std;

ifstream cin("rj.in");
ofstream cout("rj.out");

const int nmax = 1e2 + 5;

int dx[] = {-1, -1, -1, 0, 1, 1, 1, 0};
int dy[] = {-1, 0, 1, 1, 1, 0, -1, -1};

int n, m, xr, yr, xj, yj, mn[nmax][nmax];
bool aa[nmax][nmax];
char a[nmax];

void read(){
    cin >> n >> m;
    cin.get();

    for(int i = 1; i <= n; i++){
        cin.getline(a, m + 1);

        for(int j = 0; j < m; j++){
            if(a[j] == 'R')
                xr = i, yr = j + 1;
            else if(a[j] == 'J')
                xj = i, yj = j + 1;

            if(a[j] != 'X')
                aa[i][j + 1] = 1;
        }
    }


    /**for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++)
            cout << aa[i][j];
        cout << "\n";
    }*/
}

bool ok(int l, int c){
     return (l && c && l <= n && c <= m && aa[l][c]);
}

void pos(int ans, int l, int c){
    if(mn[l][c] == ans){
        cout << l << " " << c;
        return;
    }
    for(int i = 0; i < 8; i++){
        int x = l + dx[i];
        int y = c + dy[i];

        if(mn[x][y] == mn[l][c] - 1){
            pos(ans, x, y);
            return;
        }
    }
}

void calc(){
    mn[xr][yr] = 1;
    queue <per> q;
    q.push({xr, yr});

    bool found = false;

    while(!q.empty() && !found){
        per cell = q.front();
        q.pop();

        for(int i = 0; i < 8 && !found; i++){
            int l = cell.first + dx[i];
            int c = cell.second + dy[i];

            if(ok(l, c) && !mn[l][c]){
                mn[l][c] = mn[cell.first][cell.second] + 1;
                q.push({l, c});
            }

            if(l == xj && c == yj)
                found = true;
        }
    }

    int ans = mn[xj][yj] / 2 + mn[xj][yj] % 2;
    cout << ans << " ";
    pos(ans, xj, yj);
}

int main()
{
    read();
    calc();

    return 0;
}