Cod sursa(job #2155874)

Utilizator NicolaalexandraNicola Alexandra Mihaela Nicolaalexandra Data 8 martie 2018 11:05:13
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.62 kb
#include <fstream>
#define DIM 101
using namespace std;

ifstream fin ("rj.in");
ofstream fout ("rj.out");

int n,m,i,j,ic,jc,iv,jv,rx,ry,jx,jy,px,py,d,minim,p,u;
int a[DIM][DIM],b[DIM][DIM],c[2][DIM*DIM+2];
int di[] = {-1,-1,-1, 0,0, 1,1,1};
int dj[] = {-1, 0, 1,-1,1,-1,0,1};
char s[103];
int main (){

    fin>>n>>m;
    for (i=1;i<=n;i++){
        fin.get ();
        fin.get (s,103);
        for (j=0;j<m;j++){
            if (s[j] == 'X'){
                a[i][j+1] = -1;
                b[i][j+1] = -1;
                continue;
            }
            if (s[j] == 'R'){
                rx = i;
                ry = j+1;
                continue;
            }
            if (s[j] == 'J'){
                jx = i;
                jy = j+1;
            }
        }
    }

    /// bordam matricea cu -1
    for (i=0;i<=m+1;i++){
        a[0][i] = a[n+1][i] = -1;
        b[0][i] = b[n+1][i] = -1;
    }
    for (i=1;i<=n+1;i++){
        a[i][0] = a[i][m+1] = -1;
        b[i][0] = b[i][m+1] = -1;
    }

    /// facem lee din R apoi din J
    c[0][1] = rx;
    c[1][1] = ry;
    p = u = 1;
    a[rx][ry] = 1;
    while (p <= u){
        ic = c[0][p];
        jc = c[1][p];
        for (d=0;d<=7;d++){
            iv = ic + di[d];
            jv = jc + dj[d];
            if (a[iv][jv] == 0){
                a[iv][jv] = 1 + a[ic][jc];
                u++;
                c[0][u] = iv;
                c[1][u] = jv;
            }
        }

        p++;
    }

    c[0][1] = jx;
    c[1][1] = jy;
    p = u = 1;
    b[jx][jy] = 1;
    while (p <= u){
        ic = c[0][p];
        jc = c[1][p];
        for (d=0;d<=7;d++){
            iv = ic + di[d];
            jv = jc + dj[d];
            if (b[iv][jv] == 0){
                b[iv][jv] = 1 + b[ic][jc];
                u++;
                c[0][u] = iv;
                c[1][u] = jv;
             }
        }

        p++;
    }

    minim = 2000000000;
    for (i=1;i<=n;i++)
        for (j=1;j<=m;j++){
            if (a[i][j] != -1 && a[i][j] != 0)
                if (a[i][j] == b[i][j]){ /// aici e un posibil punct de intalnire
                    if (a[i][j] < minim){
                        minim = a[i][j];
                        px = i;
                        py = j;
                    }
                }
        }
    /*for (i=1;i<=n;i++){
        for (j=1;j<=m;j++)
            fout<<a[i][j]<<" ";
        fout<<"\n";
    }
    for (i=1;i<=n;i++){
        for (j=1;j<=m;j++)
            fout<<b[i][j]<<" ";
        fout<<"\n";
    }*/
    fout<<minim<<" "<<px<<" "<<py;

    return 0;
}