Cod sursa(job #2120730)

Utilizator PredaBossPreda Andrei PredaBoss Data 2 februarie 2018 20:24:05
Problema Rj Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.63 kb
#include <bits/stdc++.h>

using namespace std;
ifstream fin("rj.in");
ofstream fout("rj.out");
int i,j,n,m,d,x,y,k;
short dx[]={1,1,1,0,0,-1,-1,-1};
short dy[]={1,-1,0,1,-1,1,-1,0};
queue<pair<int,int> >q1,q2;
short f1[101][101],f2[101][101];
void rezultat()
{d=INT_MAX;
int px,py;
    for(i=1;i<=n;i++){
        for(j=1;j<=m;j++){
            if(f1[i][j]<d && f1[i][j]>0 && f2[i][j]==f1[i][j]){
               d=f1[i][j];
               px=i;
               py=j;
            }
        }
    }
    fout<<d<<" "<<px<<" "<<py;
}
void leej()
{k=0;
    while(!q2.empty())
    {
        int px=q2.front().first;
        int py=q2.front().second;
        q2.pop();
        for(i=0;i<=7;i++){
            if(f2[px+dx[i]][py+dy[i]]==-1)
                continue;
            if(f2[px+dx[i]][py+dy[i]]!=0 && f2[px+dx[i]][py+dy[i]]<f2[px][py]+1)
                continue;
            if(px+dx[i]==0 || py+dy[i]==0 || px+dx[i]>n || py+dy[i]>m)
                continue;
                if(f2[px][py]+1>d){
                    k=1;
                    break;
                }
            q2.push({px+dx[i],py+dy[i]});
            f2[px+dx[i]][py+dy[i]]=f2[px][py]+1;}
            if(k==1)
                break;
    }
}
void leer()
{k=0;
    while(!q1.empty())
    {
        int px=q1.front().first;
        int py=q1.front().second;
        q1.pop();
        for(i=0;i<=3;i++){
            if(f1[px+dx[i]][py+dy[i]]==-1)
                continue;
            if(f1[px+dx[i]][py+dy[i]]!=0 && f1[px+dx[i]][py+dy[i]]<f1[px][py]+1)
                continue;
            if(px+dx[i]==0 || py+dy[i]==0 || px+dx[i]>n || py+dy[i]>m)
                continue;
                if(px+dx[i]==x && py+dy[i]==y){
                    d=f1[px][py]+1;
                    k=1;
                    break;
                }
            q1.push({px+dx[i],py+dy[i]});
            f1[px+dx[i]][py+dy[i]]=f1[px][py]+1;}
            if(k==1)
                break;
    }
}
void cetire()
{char a[101];
    fin>>n>>m;
    fin.get();
    for(i=1;i<=n;i++){
            fin.get(a,101);
            fin.get();
        for(j=0;j<m;j++){
            if(a[j]=='X'){
                f1[i][j+1]=f2[i][j+1]=-1;
                continue;
            }
            if(a[j]=='R'){
                q1.push({i,j+1});
                f1[i][j+1]=1;
                continue;
            }
            if(a[j]=='J'){
                    f2[i][j+1]=1;
                    x=i;
                    y=j+1;
                q2.push({i,j+1});
            }
        }
    }
}
int main()
{cetire();
leer();
leej();
rezultat();
    return 0;
}