Cod sursa(job #2880373)

Utilizator 11111theodorSebastian Theodor-Ioan 11111theodor Data 29 martie 2022 17:36:18
Problema Rj Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.73 kb
#include <iostream>
#include <fstream>
#include <cstring>
#include <vector>
#include <algorithm>
#include <bitset>
#include <cmath>
#include <queue>
#define pii pair <int, int>

using namespace std;

const int oo = 2e9;
const int MAX = 1e9;
ifstream fin("rj.in");
ofstream fout("rj.out");

queue <pii> q;
int n, m, ri, rj, ji, jj;
char a[105][105];
int d1[105][105], d2[105][105];
int dx[] = { -1, -1, -1, 0, 0, 1, 1, 1 };
int dy[] = { -1, 0, 1, -1, 1, -1, 0, 1 };

void read() {
    fin >> n >> m;
    int linie = 0;
    while (fin.getline(a[linie] + 1, 105)) {
        for (int j = 1; j <= m; j++) {
            if (a[linie][j] == 'R')
                ri = linie, rj = j;
            else if (a[linie][j] == 'J')
                ji = linie, jj = j;
        }
        linie++;
    }
    /*
    for (int i = 1; i <= n; i++, cout << endl)
        for (int j = 1; j <= m; j++)
            cout << a[i][j];
            */
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            d1[i][j] = oo, d2[i][j] = oo;

}


bool kekw(int i, int j) {
    if (i < 1 || i > n || j < 1 || j > m)
        return false;
    return true;
}


void Lee() {
    q.push({ ri,rj });
    d1[ri][rj] = 1;
    while (!q.empty()) {
        int i, j;
        i = q.front().first;
        j = q.front().second;
        q.pop();
        for (int k = 0; k < 8; k++) {
            int x = i + dx[k];
            int y = j + dy[k];
            if (kekw(x, y) && a[x][y] != 'X' && d1[x][y] > d1[i][j] + 1) {
                //cout << "bazinga";
                d1[x][y] = d1[i][j] + 1;
                q.push({ x, y });
            }
        }
    }

    q.push({ ji,jj });
    d2[ji][jj] = 1;
    while (!q.empty()) {
        int i, j;
        i = q.front().first;
        j = q.front().second;
        q.pop();
        for (int k = 0; k < 8; k++) {
            int x = i + dx[k];
            int y = j + dy[k];
            if (kekw(x, y) && a[x][y] != 'X' && d2[x][y] > d2[i][j] + 1) {
                d2[x][y] = d2[i][j] + 1;
                q.push({ x, y });
            }
        }
    }
}

int main() {
    read();
    Lee();

    /*for (int i = 1; i <= n; i++, cout << endl)
        for (int j = 1; j <= m; j++)
            cout << d1[i][j] << ' ';
    cout << endl;
    for (int i = 1; i <= n; i++, cout << endl)
        for (int j = 1; j <= m; j++)
            cout << d2[i][j] << ' ';*/

    int val = oo, sol1 = 0, sol2 = 0;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            if (d1[i][j] == d2[i][j] && d1[i][j] && d1[i][j] < val)
                val = d1[i][j], sol1 = i, sol2 = j;

    fout << val << ' ' << sol1 << ' ' << sol2;
    return 0;
}