Cod sursa(job #2747540)

Utilizator mateilazarescumateilazarescu mateilazarescu Data 29 aprilie 2021 12:59:22
Problema Rj Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.68 kb
#include<bits/stdc++.h>
using namespace std;
ifstream fin("rj.in");
ofstream fout("rj.out");
int n,m,i,j,rx,ry,jx,jy,minn,fx,fy;
int mat[105][105],marcat[3][105][105];
char sir[105];
int vi[8]={-1,-1,-1,0,1,1,1,0};
int vj[8]={-1,0,1,1,1,0,-1,-1};
queue<pair<int,int> > q;
bool ok(int x,int y)
{
    if(x<1 or x>n or y<1 or y>m)
        return false;
    if(mat[x][y]==1)
        return false;
    return true;
}
void algFill(int x,int y,int c)
{
    int i,j,in,jn,d;
    q.push(make_pair(x,y));
    marcat[c][x][y]=1;
    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 marcat[c][in][jn]==0)
            {
                marcat[c][in][jn]=marcat[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=1;j<=m;j++)
        {
            if(sir[j-1]=='X') mat[i][j]=1;
            if(sir[j-1]=='R') rx=i,ry=j;
            if(sir[j-1]=='J') jx=i,jy=j;
        }
    }
    algFill(rx,ry,1);
    algFill(jx,jy,2);
    minn=9999999;
    for(i=1;i<=n;i++)
    {
        for(j=1;j<=m;j++)
        {
            if(marcat[1][i][j]==marcat[2][i][j] and mat[i][j]==0 and marcat[1][i][j]!=0)
            {
                if(minn>marcat[1][i][j])
                {
                    minn=marcat[1][i][j];
                    fx=i,fy=j;
                }
            }
        }
    }
    fout<<minn<<" "<<fx<<" "<<fy;
    return 0;
}