Cod sursa(job #3297180)

Utilizator TimofeiFilipTimofei Filip Emanuel TimofeiFilip Data 21 mai 2025 21:08:20
Problema Rj Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.18 kb
#include <bits/stdc++.h>
using namespace std;

const int N = 105;
int n, m;
char mat[N][N];
int distR[N][N], distJ[N][N];
int iR, jR, iJ, jJ;

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

bool inside(int x, int y)
{
    return x >= 1 && x <= n && y >= 1 && y <= m;
}

void bfs(int si, int sj, int dist[N][N])
{
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            dist[i][j] = -1;

    queue<pair<int, int>> q;
    q.push({si, sj});
    dist[si][sj] = 1;

    while (!q.empty())
    {
        int x = q.front().first;
        int y = q.front().second;
        q.pop();

        for (int d = 0; d < 8; d++)
        {
            int nx = x + dx[d];
            int ny = y + dy[d];
            if (inside(nx, ny) && mat[nx][ny] != 'X' && dist[nx][ny] == -1)
            {
                dist[nx][ny] = dist[x][y] + 1;
                q.push({nx, ny});
            }
        }
    }
}

int main()
{
    freopen("rj.in", "r", stdin);
    freopen("rj.out", "w", stdout);

    cin >> n >> m;
    cin.ignore();

    for (int i = 1; i <= n; i++)
    {
        string line;
        getline(cin, line);
        for (int j = 1; j <= m; j++)
        {
            mat[i][j] = line[j - 1];
            if (mat[i][j] == 'R')
            {
                iR = i;
                jR = j;
            }
            else if (mat[i][j] == 'J')
            {
                iJ = i;
                jJ = j;
            }
        }
    }

    bfs(iR, jR, distR);
    bfs(iJ, jJ, distJ);

    int tmin = INT_MAX;
    int x_ans = -1, y_ans = -1;

    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            if (distR[i][j] != -1 && distR[i][j] == distJ[i][j])
            {
                if (distR[i][j] < tmin ||
                    (distR[i][j] == tmin && (i < x_ans || (i == x_ans && j < y_ans))))
                {
                    tmin = distR[i][j];
                    x_ans = i;
                    y_ans = j;
                }
            }
        }
    }

    cout << tmin << " " << x_ans << " " << y_ans << "\n";

    return 0;
}