Cod sursa(job #2421726)

Utilizator bluestorm57Vasile T bluestorm57 Data 15 mai 2019 21:48:55
Problema Rj Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 4.86 kb
#include <fstream>
#include <deque>
#include <cstring>

using namespace std;

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

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

struct pozitie{
    int lin, col;
};

pozitie a,b,c;
char s[102];
int n,m;
int mat[105][105], sup[105][105];


void afisaremat(){
    int i,j;
    for(i=1; i<=n; i++){
        for(j=1; j<=m; j++)
            g<<mat[i][j]<<" ";
        g<<"\n";
    }
}

void afisaresup(){
    int i,j;
    for(i=1; i<=n; i++){
        for(j=1; j<=m; j++)
            g<<sup[i][j]<<" ";
        g<<"\n";
    }
}

bool ok(int x, int y, int a, int b){
    int i,j;
    for(i=0; i<8; i++){
        int nx=x+dx[i];
        int ny=y+dy[i];
        for(j=0; j<8; j++){
            int na=a+dx[j];
            int nb=b+dy[j];
            if(na==nx && nb==ny && !mat[nx][ny])
                return 1;
        }
    }
    return 0;

}

bool notvecine(int x, int y, int a, int b){
    if(a==x && (b==y+1 || b==y-1)) return 0;
    if(b==y && (a==x+1 || a==x-1)) return 0;
    return 1;
}

int undevecine(int x, int y, int a, int b){
    int i;
    for(i=0; i<8; i++){
        int nx=x+dx[i];
        int ny=y+dy[i];
        for(int j=0; j<8; j++){
            int na=a+dx[j];
            int nb=b+dy[j];
            if(na==nx && nb==ny && !mat[nx][ny])
                return i;
        }
    }
}

void Lee(){
   deque<int>ax,ay, bx,by;
    int i, xa, ya, xb, yb;
    ax.push_back(a.lin);
    ay.push_back(a.col);
    bx.push_back(b.lin);
    by.push_back(b.col);
    mat[a.lin][a.col]=mat[b.lin][b.col]=1;

    while(!ax.empty() && !bx.empty()/* && !mat[b.lin][b.col]*/){
        xa=ax.front();
        ya=ay.front();
        xb=bx.front();
        yb=by.front();
        ax.pop_front();
        ay.pop_front();
        bx.pop_front();
        by.pop_front();

        if(ok(xa,ya,xb,yb) /*&& notvecine(xa,ya,xb,yb)*/){
            //g<<xa<<" "<<ya<<" "<<xb<<" "<<yb<<"\n";
        i=undevecine(xa,ya,xb,yb);
        g<<mat[xa][ya]+1<<" "<<xa+dx[i]<<" "<<ya+dy[i];

        while(!ax.empty())
            ax.pop_back();
        }
        else
        for(i=0; i<8; i++){
            int nax=xa+dx[i];
            int nay=ya+dy[i];
            int nbx=xb+dx[i];
            int nby=yb+dy[i];

                if(!mat[nax][nay]){
                   // g<<nax<<" "<<nay<<"\n";
                    mat[nax][nay]=mat[xa][ya]+1;
                    ax.push_back(nax);
                    ay.push_back(nay);
                }
               if(!mat[nbx][nby]){
                   // g<<nbx<<" "<<nby<<"\n";
                    mat[nbx][nby]=mat[xb][yb]+1;
                    bx.push_back(nbx);
                    by.push_back(nby);
                }

            }
        }


}

void Leemat(){
    int i,x,y;
    deque<int>qx, qy;
    qx.push_back(a.lin);
    qy.push_back(a.col);
    mat[a.lin][a.col]=1;
    while(!qx.empty() /*&& !mat[b.lin][b.col]*/){
        x=qx.front();
        y=qy.front();
        qx.pop_front();
        qy.pop_front();

        for(i=0; i<8; i++){
            int nx=dx[i]+x;
            int ny=y+dy[i];
            if(!mat[nx][ny]){
                mat[nx][ny]=mat[x][y]+1;
                qx.push_back(nx);
                qy.push_back(ny);
            }
        }
    }

}

void Leesup(){
    int i,x,y;
    deque<int>qx, qy;
    qx.push_back(b.lin);
    qy.push_back(b.col);
    sup[b.lin][b.col]=1;
    while(!qx.empty() /*&& !sup[a.lin][a.col]*/){
        x=qx.front();
        y=qy.front();
        qx.pop_front();
        qy.pop_front();

        for(i=0; i<8; i++){
            int nx=dx[i]+x;
            int ny=y+dy[i];
            if(!sup[nx][ny]){
                sup[nx][ny]=sup[x][y]+1;
                qx.push_back(nx);
                qy.push_back(ny);
            }
        }
    }

}

int main(){
    int i,j;
    f>>n>>m;
    f.getline(s,1);
    for(i=1; i<=n; i++){
    f.getline(s,102);
    for(j=1; j<=m; j++){

        if(s[j-1]=='X')
        mat[i][j]=-1;
        else
            if(s[j-1]=='R'){
                a.lin=i;
                a.col=j;
            }
            else
            if(s[j-1]=='J'){
                b.lin=i;
                b.col=j;
            }
            else
                mat[i][j]=0;

         sup[i][j]=mat[i][j];}
    }
     for(i=0; i<=n+1; i++)
        sup[i][0]=sup[i][m+1]=mat[i][0]=mat[i][m+1]=-1;
     for(j=1; j<=m; j++)
        sup[0][j]=sup[n+1][j]=mat[0][j]=mat[n+1][j]=-1;



     Leemat();
     Leesup();

// afisaremat();
 //afisaresup();
 int tmin=n*m*n;
 for(i=1; i<=n; i++)
    for(j=1; j<=m; j++)
 if(mat[i][j]==sup[i][j] && mat[i][j]>0 && mat[i][j]<tmin){
    tmin=mat[i][j];
    c.lin=i;
    c.col=j;
 }

    g<<mat[c.lin][c.col]<<" "<<c.lin<<" "<<c.col;

    return 0;
}