Cod sursa(job #2741182)

Utilizator Mihai_PredaPreda Mihai Dragos Mihai_Preda Data 15 aprilie 2021 17:42:29
Problema Rj Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.97 kb
#include <iostream>
#include <fstream>
#include <queue>
#include <unordered_map>

using namespace std;

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

char mat[102][102], rX, rY, jX, jY;
int n, m;
void lee(int startX, int startY, int dist[102][102])
{
    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({startX, startY});
    dist[startX][startY] = 0;

    while(q.empty() == false)
    {
        pair<int, int> p = q.front();
        q.pop();

        // (p.first, p.second)
        for(int d = 0; d < 4; d++)
        {
            int newX = p.first + dx[d];
            int newY = p.second + dy[d];
            if(newX >= 1 && newY >= 1 && newX <= n && newY <= m &&
               mat[newX][newY] != 'X' && dist[newX][newY] == -1)
            {
                dist[newX][newY] = dist[p.first][p.second] + 1;
                q.push({newX, newY});
            }
        }
    }
}

int romeo[102][102], julieta[102][102];
int main()
{
    ifstream in("rj.in");
    ofstream out("rj.out");
    in >> n >> m;
    for(int i = 1; i <= n; ++i)
    {
        in.get();
        in.get(mat[i]+1, m+1, '\n');
    }
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++)
        {
            if(mat[i][j] == 'R')
            {
                rX = i;
                rY = j;
            }
            else if(mat[i][j] == 'J')
            {
                jX = i;
                jY = j;
            }
        }

    lee(rX, rY, romeo);
    lee(jX, jY, julieta);

    int tmin = n*m, x, y;
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++)
        {
            if(romeo[i][j] != -1 && romeo[i][j] == julieta[i][j] && romeo[i][j] < tmin)
            {
                tmin = romeo[i][j];
                x = i;
                y = j;
            }
        }
    out << tmin << " " << x << " " << y;
    return 0;
}