Cod sursa(job #2668670)

Utilizator jucatorulGrigore George Alexandru jucatorul Data 5 noiembrie 2020 08:06:40
Problema Rj Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.09 kb
#include <bits/stdc++.h>

using namespace std;

ifstream fin("rj.in");
ofstream fout("rj.out");

int romeo[102][102], julieta[102][102];

int x[8] = {-1, 0, 1, -1, 1, -1, 0, 1};
int y[8] = {-1, -1, -1, 0, 0, 1, 1, 1};

queue<pair<int, int>> q;
int n, m, rx, ry, jx, jy;

void bfs(int mat[102][102], int start_x, int start_y)
{
    int next_x, next_y, index, curr_x, curr_y;
    q.push({start_x, start_y});
    while (!q.empty())
    {
        curr_x = q.front().first;
        curr_y = q.front().second;
        q.pop();

        for (index = 0; index < 8; index++)
        {
            next_x = curr_x + x[index];
            next_y = curr_y + y[index];

            if (next_x >= 1 && next_x <= n && next_y >= 1 && next_y <= m)
                if (mat[next_x][next_y] == 0)
                {
                    mat[next_x][next_y] = mat[curr_x][curr_y] + 1;
                    q.push({next_x, next_y});
                }
        }
    }
}
int main()
{
    int i, j;
    char s[101];
    fin >> n >> m;
    fin.get();
    for (i = 1; i <= n; i++)
    {
        fin.getline(s, 101);
        for (j = 0; j < m; j++)
        {
            if (s[j] == 'R')
            {
                romeo[i][j + 1] = 1;
                rx = i;
                ry = j + 1;
            }
            else if (s[j] == 'J')
            {
                julieta[i][j + 1] = 1;
                jx = i;
                jy = j + 1;
            }
            else if (s[j] == 'X')
            {
                romeo[i][j + 1] = -1;
                julieta[i][j + 1] = -1;
            }
        }
    }

    bfs(romeo, rx, ry);
    bfs(julieta, jx, jy);

    int ans = INT_MAX, meeting_x = 0, meeting_y = 0;
    for (i = 1; i <= n; i++)
        for (j = 1; j <= m; j++)
        {
            if (romeo[i][j] == julieta[i][j] && romeo[i][j] < ans && julieta[i][j] > 0)
            {
                ans = romeo[i][j];
                meeting_x = i;
                meeting_y = j;
            }
        }
    fout << ans << " " << meeting_x << " " << meeting_y;
    return 0;
}