Cod sursa(job #2660086)

Utilizator marcumihaiMarcu Mihai marcumihai Data 18 octombrie 2020 09:28:19
Problema Rj Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.53 kb
#include <bits/stdc++.h>

using namespace std;
ifstream f ("rj.in");
ofstream g ("rj.out");

int n,m;
int mt[205][205];
int ro[205][205];
int ju[205][205];
char c[10001];
int di[8]={-1,-1,0,1,1,1,0,-1};
int dj[8]={0,1,1,1,0,-1,-1,-1};
int dist;
queue <pair<int,int>> Q;
int ok1(int i, int j)
{
    if(i<1 || j<1 || i>n || j>m)
        return 0;
    if(ro[i][j]!=0)
        return 0;
    return 1;

}
int ok2(int i, int j)
{
    if(i<1 || j<1 || i>n || j>m)
        return 0;
    if(ju[i][j]!=0)
        return 0;
    return 1;

}
void LeeRomeo (int x,int y)
{
    Q.push(make_pair(x,y));
    while(!Q.empty())
    {
        int i=Q.front().first;
        int j=Q.front().second;
        for(int x=0;x<8;++x)
        {
            if(ok1(i+di[x],j+dj[x]))
            {
                Q.push({i+di[x],j+dj[x]});
                ro[i+di[x]][j+dj[x]]=ro[i][j]+1;

            }

        }
        Q.pop();
    }
}

void LeeJulieta (int x,int y)
{
    Q.push(make_pair(x,y));
    while(!Q.empty())
    {
        int i=Q.front().first;
        int j=Q.front().second;
        for(int x=0;x<8;++x)
        {
            if(ok2(i+di[x],j+dj[x]))
            {
                Q.push({i+di[x],j+dj[x]});
                ju[i+di[x]][j+dj[x]]=ju[i][j]+1;

            }
        }
        Q.pop();
    }
}
int main()
{
    f>>n>>m;
     f.getline(c , 300);
    for(int i=1;i<=n;++i)
    {
        f.getline(c , 300);
        for(int j=0;j<m;++j)
        {

            if(c[j]==' ')
                mt[i][j+1]=0;
            if(c[j]=='X')
               {
                   mt[i][j+1]=-1;
                   ro[i][j+1]=mt[i][j+1];
                   ju[i][j+1]=mt[i][j+1];

               }
            if(c[j]=='R')
                mt[i][j+1]=9999;
            if(c[j]=='J')
                mt[i][j+1]=-9999;

        }
    }
    for(int i=1;i<=n;++i)
    {
        for(int j=1;j<=m;++j)
        {
            if(mt[i][j]==9999)
                LeeRomeo(i,j);
            if(mt[i][j]==-9999)
                LeeJulieta(i,j);

        }
    }
    int mini=9999999;
    int imax=0;
    int jmax=0;


    for(int i=1;i<=n;++i)
    {
        for(int j=1;j<=m;++j)
            {
                if(ro[i][j]==ju[i][j] && ro[i][j]<mini && ro[i][j]!=-1 && ro[i][j]!=0)
                {
                    mini=ro[i][j];
                    imax=i;
                    jmax=j;
                }
            }
    }
    g<<(ro[imax][jmax]+1)<<" "<<imax<<" "<<jmax;
    return 0;
}