Cod sursa(job #2208412)

Utilizator georgitTreista Georgiana georgit Data 29 mai 2018 17:56:32
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.01 kb
#include <fstream>
#include <queue>

using namespace std;
queue < pair<int, int> > Q;
queue < pair<int, int> > C;
int cost1[105][105],cost2[105][105],n,m;
bool a[105][105],b[105][105];
int dx[]={0,0,1,-1,-1,-1,1,1};
int dy[]={1,-1,0,0,1,-1,1,-1};
bool inside(int x,int y)
{
    return (x>=1 and x<=n and y>=1 and y<=m);
}
void Lee1()
{
    while(!Q.empty())
    {
        pair <int, int> k=Q.front();
        int i=k.first;
        int j=k.second;
        Q.pop();
        for(int d=0;d<8;d++)
        {
            int l=i+dx[d];
            int c=j+dy[d];
            if(inside(l,c) and a[l][c]==0)
            {
                    a[l][c]=1;
                    cost1[l][c]=cost1[i][j]+1;
                    Q.push(make_pair(l,c));

            }
        }
    }
}
void Lee2()
{
    while(!C.empty())
    {
        pair <int, int> k=C.front();
        int i=k.first;
        int j=k.second;
        C.pop();
        for(int d=0;d<8;d++)
        {
            int l=i+dx[d];
            int c=j+dy[d];
            if(inside(l,c) and b[l][c]==0)
            {
                    b[l][c]=1;
                    cost2[l][c]=cost2[i][j]+1;
                    C.push(make_pair(l,c));

            }
        }
    }
}
int main()
{
    ifstream f("rj.in");
    ofstream g("rj.out");
    f>>n>>m;
    char c[105];
    f.get();
    for(int i=1;i<=n;i++)
    {
        f.getline(c,m+1);
        for(int j=1;j<=m;j++)
        {
            if(c[j-1]=='X') {a[i][j]=1;b[i][j]=1;}
            if(c[j-1]=='R') {cost1[i][j]=1;Q.push(make_pair(i,j));}
            if(c[j-1]=='J') {cost2[i][j]=1;C.push(make_pair(i,j));}
        }
    }
    Lee1();
    Lee2();
    int mini=100000,lin,col;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
    {
        if(cost1[i][j]==cost2[i][j] and cost1[i][j]!=0 and cost1[i][j]<mini)
        {
            mini=cost1[i][j];
            lin=i;
            col=j;
        }

    }
    g<<mini<<" "<<lin<<" "<<col;
    return 0;
}