Cod sursa(job #2770319)

Utilizator mateilazarescumateilazarescu mateilazarescu Data 20 august 2021 14:59:21
Problema Rj Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.66 kb
#include<fstream>
#include<queue>
using namespace std;
ifstream fin("rj.in");
ofstream fout("rj.out");
int n,m,i,j,i1,j1,i2,j2,minn,x,y;
int mat[105][105],drum[3][105][105];
int vi[8]={-1,-1,0,1,1,1,0,-1};
int vj[8]={0,1,1,1,0,-1,-1,-1};
char sir[105];
queue<pair<int,int> > q;
bool ok(int x,int y)
{
    if(x<1 or y<1 or x>n or y>m)
        return false;
    if(mat[x][y]==1)
        return false;
    return true;
}
void algLee(int x,int y,int c)
{
    drum[c][x][y]=1;
    q.push(make_pair(x,y));
    int d,i,j,in,jn;
    while(!q.empty())
    {
        i=q.front().first;
        j=q.front().second;
        q.pop();
        for(d=0;d<8;d++)
        {
            in=i+vi[d],jn=j+vj[d];
            if(ok(in,jn) and drum[c][in][jn]==0)
            {
                drum[c][in][jn]=drum[c][i][j]+1;
                q.push(make_pair(in,jn));
            }
        }
    }
}
int main()
{
    fin>>n>>m;
    fin.get();
    for(i=1;i<=n;i++)
    {
        fin.get(sir,105);
        fin.get();
        for(j=0;j<m;j++)
        {
            if(sir[j]=='X')
                mat[i][j+1]=1;
            if(sir[j]=='R') i1=i,j1=j+1;
            if(sir[j]=='J') i2=i,j2=j+1;
        }
    }
    algLee(i1,j1,1);
    algLee(i2,j2,2);
    minn=999999999;
    for(i=1;i<=n;i++)
    {
        for(j=1;j<=m;j++)
        {
            if(drum[1][i][j]==drum[2][i][j] and drum[1][i][j]!=0)
            {
                if(minn>drum[1][i][j])
                {
                    minn=drum[1][i][j];
                    x=i,y=j;
                }

            }
        }
    }
    fout<<minn<<" "<<x<<" "<<y<<'\n';
    return 0;
}