Cod sursa(job #1704968)

Utilizator anghelus_vladAnghelus Ionut Vlad anghelus_vlad Data 19 mai 2016 18:04:13
Problema Rj Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.06 kb
#include <fstream>

using namespace std;

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

int n, m, i, j, k, xr, yr, xj, yj, xf, yf, minim, ic, sc, l9, c9;
int rom[103][103], jul[103][103], dl[]={-1, -1, 0, 1, 1, 1, 0, -1}, dc[]={0, 1, 1, 1, 0, -1, -1, -1};
char c;
struct element
{
    int lin, col, d;
}C[31000], X;

int main()
{
    fin >> n >> m;
    fin.get();
    for(i=1; i<=n; ++i)
    {
        for(j=1; j<=m; ++j)
        {
            fin.get(c);
            if(c=='X')
                rom[i][j]=jul[i][j]=-1;
            else if(c=='R')
                xr=i, yr=j;
            else if(c=='J')
                xj=i, yj=j;
        }
        fin.get();
    }
    // bordare
    for(i=0; i<=max(n, m)+1; ++i)
    {
        rom[i][0]=rom[i][m+1]=rom[0][i]=rom[n+1][i]=-1;
        jul[i][0]=jul[i][m+1]=jul[0][i]=jul[n+1][i]=-1;
    }
    ic=0; sc=0;
    C[sc].lin=xr; C[sc].col=yr; C[sc].d=1;
    rom[xr][yr]=1;
    while(ic <= sc)
    {
        X=C[ic]; ic++;
        for(k=0; k<8; ++k)
        {
            l9=X.lin + dl[k];
            c9=X.col + dc[k];
            if(rom[l9][c9]==0)
            {
                sc++;
                C[sc].lin=l9;
                C[sc].col=c9;
                C[sc].d=X.d+1;
                rom[l9][c9]=X.d+1;
            }
        }
    }
    ic=0; sc=-1;
    sc++;
    C[sc].lin=xj; C[sc].col=yj; C[sc].d=1;
    jul[xj][yj]=1;
    while(ic <= sc)
    {
        X=C[ic]; ic++;
        for(k=0; k<8; ++k)
        {
            l9=X.lin + dl[k];
            c9=X.col + dc[k];
            if(jul[l9][c9]==0)
            {
                sc++;
                C[sc].lin=l9;
                C[sc].col=c9;
                C[sc].d=X.d+1;
                jul[l9][c9]=X.d+1;
            }
        }
    }
    minim=500;
    for(i=1; i<=n; ++i)
        for(j=1; j<=m; ++j)
        {
            if(rom[i][j]==jul[i][j] && rom[i][j]!=-1 && rom[i][j]<minim)
                xf=i, yf=j, minim=rom[i][j];
        }
    fout << xf << " " << yf << " " << minim << '\n';
    return 0;
}