Cod sursa(job #2286669)

Utilizator 0SiSBesliu Radu-Stefan 0SiS Data 20 noiembrie 2018 17:11:24
Problema Rj Scor 50
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.25 kb
#include <fstream>

using namespace std;
ifstream f("rj.in");
ofstream g("rj.out");

int dx[]={-1,-1,0,1,1,1,0,-1};
int dy[]={0,1,1,1,0,-1,-1,-1};

char linie[101];
int n,m,rx,ry,jx,jy,matrice[101][101],matrice2[101][101];
int x[105*105],y[105*105],v[105*105],ok,p,q,a,b,i,j,min1,nr1,nr2;

int main()
{
    f>>n>>m;
    f.get();
    for(int i=1;i<=n;i++){
        f.getline(linie,102);
        for(int j=0;j<m;j++){
            if(linie[j]=='X') matrice[i][j+1]=-1;
            else matrice[i][j+1]=0;
            if(linie[j]=='R'){
                rx=i;
                ry=j+1;
            }
            else if(linie[j]=='J'){
                jx=i;
                jy=j+1;
            }
        }
    }
    for(int i=0;i<=n+1;i++) matrice[i][0]=matrice[i][m+1]=-1;
    for(int j=0;j<=m+1;j++) matrice[0][j]=matrice[n+1][j]=-1;
    for(int i=0;i<=n+1;i++){
        for(int j=0;j<=m+1;j++){
            matrice2[i][j]=matrice[i][j];
        }
    }
    p=q=1;
    x[1]=rx;
    y[1]=ry;
    v[1]=1;
    ok=0;
    while(p<=q && !ok){
        a=x[p];
        b=y[p];
        for(int k=0;k<8;k++){
            i=a+dx[k];
            j=b+dy[k];
            if(matrice[i][j]==0){
                q++;
                x[q]=i;
                y[q]=j;
                v[q]=v[p]+1;
                matrice[i][j]=v[p]+1;
                if(i==jx && j==jy) ok=0;
            }
        }
        p++;
    }
    p=q=1;
    x[1]=jx;
    y[1]=jy;
    v[1]=1;
    ok=0;
    while(p<=q && !ok){
        a=x[p];
        b=y[p];
        for(int k=0;k<8;k++){
            i=a+dx[k];
            j=b+dy[k];
            if(matrice2[i][j]==0){
                q++;
                x[q]=i;
                y[q]=j;
                v[q]=v[p]+1;
                matrice2[i][j]=v[p]+1;
                if(i==rx && j==ry) ok=0;
            }
        }
        p++;
    }
    ok=0;
    min1=2147483647;
    for(int i=1;i<=n && ok==0;i++){
        for(int j=1;j<=n && ok==0;j++){
            if(matrice[i][j]!=-1 && matrice[i][j]!=0 && matrice[i][j]==matrice2[i][j] && matrice[i][j]<min1){
                min1=matrice[i][j];
                nr1=i;
                nr2=j;
            }
        }
    }
    g<<min1<<" "<<nr1<<" "<<nr2;
}