Cod sursa(job #2660652)

Utilizator Harsa_AndreiHarsa Andrei Harsa_Andrei Data 19 octombrie 2020 23:05:33
Problema Rj Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.99 kb
#include <bits/stdc++.h>
#define INF 99999999

using namespace std;

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

int Rom[102][102], Jul[102][102], n, m, rlin, rcol, jlin, jcol;

int ml[] = {0, 0, 1, -1, 1, 1, -1, -1};
int mc[] = {1, -1, 0, 0, 1, -1, 1, -1};

queue<pair<int, int>> Q;

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

void Lee(int M[][102])
{
    while(!Q.empty())
    {
        int x = Q.front().first;
        int y = Q.front().second;
        Q.pop();

        for(int i = 0; i < 8; i++)
        {
            int xx = x + ml[i];
            int yy = y + mc[i];
            if(ok(xx,yy) && M[xx][yy] != -1 && M[xx][yy] > M[x][y] + 1)
            {
                M[xx][yy] = M[x][y] + 1;
                Q.push(make_pair(xx,yy));
            }
        }
    }
}

int main(){
    fin >> n >> m;
    char s[102];
    fin.get();
    for(int i = 1; i <= n; i++){
        fin.getline(s, m + 1);
        for(int j = 1; j <= m; j++)
        {
            if(s[j-1] == 'R')
            {
                Rom[i][j] = 0;
                rlin = i;
                rcol = j;
                Jul[i][j] = INF;
            }
            else if(s[j-1] == 'J')
            {
                Rom[i][j] = INF;
                jlin = i;
                jcol = j;
                Jul[i][j] = 0;
            }
            else if(s[j-1] == 'X')
                Rom[i][j] = Jul[i][j] = -1;
            else
                Rom[i][j] = Jul[i][j] = INF;
                        
        }
    }
    Q.push(make_pair(rlin, rcol));

    Lee(Rom);


    Q.push(make_pair(jlin, jcol));

    Lee(Jul);

    int rezl = 1, rezc = 1, mini = INF;

    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++)
        {
            if(Rom[i][j] == Jul[i][j] && Rom[i][j] != -1 && Rom[i][j] < mini)
            {
                rezl = i;
                rezc = j;
                mini = Rom[i][j];
            }
        }
    fout << Rom[rezl][rezc] + 1 << ' ' << rezl << ' ' << rezc;
}