Cod sursa(job #3297178)

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

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

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

bool inside(int i, int j)
{
    return i >= 1 && i <= n && j >= 1 && j <= n;
}

void bfs(int si, int sj, int dist[N][N])
{
    queue<pair<int, int>> q;
    q.push(make_pair(si, sj));
    dist[si][sj] = 0;

    while (!q.empty())
    {
        int i = q.front().first;
        int j = q.front().second;
        q.pop();

        for (int d = 0; d < 8; d++)
        {
            int ni = i + dx[d];
            int nj = j + dy[d];
            if (inside(ni, nj) && mat[ni][nj] != 'X' && dist[ni][nj] == -1)
            {
                dist[ni][nj] = dist[i][j] + 1;
                q.push(make_pair(ni, nj));
            }
        }
    }
}

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

    cin >> n;
    getchar();

    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            char c;
            cin.get(c);

            if (c == ' ')
            {
                mat[i][j] = 0;
            }
            else if (c == 'X')
            {
                mat[i][j] = -1;
            }
            else if (c == 'J')
            {
                iJ = i;
                jJ = j;
                mat[i][j] = 0;
            }
            else if (c == 'R')
            {
                iR = i;
                jR = j;
                mat[i][j] = c;
            }
        }
        getchar();
    }

    memset(distJ, -1, sizeof(distJ));
    memset(distR, -1, sizeof(distR));

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

    int minStep = INT_MAX;
    int ifinal = -1, jfinal = -1;

    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            if (distJ[i][j] != -1 && distJ[i][j] == distR[i][j])
            {
                if (distJ[i][j] < minStep ||
                    (distJ[i][j] == minStep && make_pair(i, j) < make_pair(ifinal, jfinal)))
                {
                    minStep = distJ[i][j];
                    ifinal = i;
                    jfinal = j;
                }
            }
        }
    }

    cout << minStep << " " << ifinal << " " << jfinal << "\n";
    return 0;
}