Cod sursa(job #2606738)

Utilizator mateilazarescumateilazarescu mateilazarescu Data 28 aprilie 2020 14:21:48
Problema Rj Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.05 kb
#include<bits/stdc++.h>
using namespace std;
ifstream fin("rj.in");
ofstream fout("rj.out");
int n,m,i,j,rPoz_x,rPoz_y,jPoz_x,jPoz_y,minn,xx,yy;
int harta[104][104],mat[3][104][104];
char sir[104];
queue <pair<int,int> > q;
int vi[8]={-1,-1,0,1,1,1,0,-1};
int vj[8]={0,1,1,1,0,-1,-1,-1};
bool ok(int x,int y,int c)
{
    if(x<1 or x>n or y<1 or y>m)
        return false;
    if(harta[x][y]==1)
        return false;
    if(mat[c][x][y]!=0)
        return false;
    return true;
}
void lee(int x,int y,int c)
{
    int d,iin,jin,ifin,jfin;
    q.push(make_pair(x,y));
    mat[c][x][y]=1;
    while(!q.empty())
    {
        iin=q.front().first;
        jin=q.front().second;
        q.pop();
        for(d=0;d<8;d++)
        {
            ifin=iin+vi[d],jfin=jin+vj[d];
            if(ok(ifin,jfin,c))
                {mat[c][ifin][jfin]=mat[c][iin][jin]+1;
                q.push(make_pair(ifin,jfin));
                }

        }
    }
}
int main()
{
    freopen("rj.in","r",stdin);
    freopen("rj.out","w",stdout);
    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]=='R')
                rPoz_x=i,rPoz_y=j+1;
            if(sir[j]=='J')
                jPoz_x=i,jPoz_y=j+1;
            if(sir[j]=='X')
                harta[i][j+1]=1;
        }
    }
    lee(rPoz_x,rPoz_y,1);
    lee(jPoz_x,jPoz_y,2);
    minn=100*100+4;
    for(i=1;i<=n;i++)
    {
        for(j=1;j<=m;j++)
        {
            if(mat[1][i][j]==mat[2][i][j] and mat[1][i][j]>1)
            {
                if(minn>mat[1][i][j])
                    minn=mat[1][i][j],xx=i,yy=j;
            }
        }
    }
    fout<<minn<<" "<<xx<<" "<<yy<<'\n';
    /*for(i=1;i<=n;i++)
    {
        for(j=1;j<=m;j++)
            fout<<mat[1][i][j]<<" ";
        fout<<'\n';
    }
    fout<<'\n';
    for(i=1;i<=n;i++)
    {
        for(j=1;j<=m;j++)
            fout<<mat[2][i][j]<<" ";
        fout<<'\n';
    }
    */
    return 0;
}