Cod sursa(job #3235998)

Utilizator tonealexandruTone Alexandru tonealexandru Data 25 iunie 2024 10:20:16
Problema Rj Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.32 kb
#include <bits/stdc++.h>
#define int long long

using namespace std;
int ro[205][205], ju[205][205], n, m;
queue<pair<int, int>> rom, juli;

void afis()
{
    for(int i=1; i<=n; i++)
    {
        for(int j=1; j<=m; j++)
            cout<<ju[i][j]<<" ";
        cout<<'\n';
    }
    cout<<'\n';

    for(int i=1; i<=n; i++)
    {
        for(int j=1; j<=m; j++)
            cout<<ro[i][j]<<" ";
        cout<<'\n';
    }
    cout<<'\n';
}

int32_t main()
{
    ifstream cin("rj.in");
    ofstream cout("rj.out");
    char ch;
    cin>>n>>m;
    for(int i=1; i<=n; i++)
    {
        cin.get(ch);
        for(int j=1; j<=m; j++)
        {
            cin.get(ch);
            if(ch=='X')
                ro[i][j]=-1, ju[i][j]=-1;
            else if(ch=='J')
                juli.push({i, j});
            else if(ch=='R')
                rom.push({i, j});
            else
                ro[i][j]=0, ju[i][j]=0;
        }
    }

    ro[rom.front().first][rom.front().second] = 1;
    while(rom.empty() == false)
    {
        int i = rom.front().first;
        int j = rom.front().second;
        rom.pop();
        //cout<<i<<" "<<j<<'\n';

        if(i+1<=n && ro[i+1][j]==0) rom.push({i+1, j}), ro[i+1][j] = ro[i][j] + 1;
        if(j+1<=m && ro[i][j+1]==0) rom.push({i, j+1}), ro[i][j+1] = ro[i][j] + 1;
        if(i-1>=1 && ro[i-1][j]==0) rom.push({i-1, j}), ro[i-1][j] = ro[i][j] + 1;
        if(j-1>=1 && ro[i][j-1]==0) rom.push({i, j-1}), ro[i][j-1] = ro[i][j] + 1;

        if(i+1<=n && j+1<=m && ro[i+1][j+1]==0) rom.push({i+1, j+1}), ro[i+1][j+1] = ro[i][j] + 1;
        if(i-1>=1 && j+1<=m && ro[i-1][j+1]==0) rom.push({i-1, j+1}), ro[i-1][j+1] = ro[i][j] + 1;
        if(i-1>=1 && j-1>=1 && ro[i-1][j-1]==0) rom.push({i-1, j-1}), ro[i-1][j-1] = ro[i][j] + 1;
        if(i+1<=n && j-1>=1 && ro[i+1][j-1]==0) rom.push({i+1, j-1}), ro[i+1][j-1] = ro[i][j] + 1;
    }

    ju[juli.front().first][juli.front().second] = 1;
    while(juli.empty() == false)
    {
        int i = juli.front().first;
        int j = juli.front().second;
        juli.pop();
        //cout<<i<<" "<<j<<'\n';

        if(i+1<=n && ju[i+1][j]==0) juli.push({i+1, j}), ju[i+1][j] = ju[i][j] + 1;
        if(j+1<=m && ju[i][j+1]==0) juli.push({i, j+1}), ju[i][j+1] = ju[i][j] + 1;
        if(i-1>=1 && ju[i-1][j]==0) juli.push({i-1, j}), ju[i-1][j] = ju[i][j] + 1;
        if(j-1>=1 && ju[i][j-1]==0) juli.push({i, j-1}), ju[i][j-1] = ju[i][j] + 1;

        if(i+1<=n && j+1<=m && ju[i+1][j+1]==0) juli.push({i+1, j+1}), ju[i+1][j+1] = ju[i][j] + 1;
        if(i-1>=1 && j+1<=m && ju[i-1][j+1]==0) juli.push({i-1, j+1}), ju[i-1][j+1] = ju[i][j] + 1;
        if(i-1>=1 && j-1>=1 && ju[i-1][j-1]==0) juli.push({i-1, j-1}), ju[i-1][j-1] = ju[i][j] + 1;
        if(i+1<=n && j-1>=1 && ju[i+1][j-1]==0) juli.push({i+1, j-1}), ju[i+1][j-1] = ju[i][j] + 1;
    }

    int minn = 2100000000, rezi, rezj;
    for(int i=1; i<=n; i++)
    {
        for(int j=1; j<=m; j++)
        {
            if(ju[i][j] == ro[i][j] && ju[i][j]!=-1 && ju[i][j]!=0)
            {
                if(ju[i][j]< minn)
                {
                    minn = ju[i][j];
                    rezi=i;
                    rezj=j;
                }
            }
        }
    }
    cout<<minn<<" "<<rezi<<" "<<rezj;



    return 0;
}