Cod sursa(job #1983923)

Utilizator mihailrazMihail Turcan mihailraz Data 22 mai 2017 20:55:15
Problema Rj Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.75 kb
#include <fstream>
#include <iomanip>
#include <queue>

using namespace std;

ifstream fi("rj.in");
ofstream fo("rj.out");
int n,m,x,y,i,j,xr,yr,xj,yj,xmin=-1,ymin=-1,mini=102*102+5;
int R[102][102],J[102][102],M[102][102];
char c;
char C[101][101];

queue <pair <int,int> > Q;

void lee(int A[102][102], int l, int c)
{
    int DI[8]={-1,-1,0,1,1,1,0,-1},DJ[8]={0,1,1,1,0,-1,-1,-1};
    for(i=0;i<=n+1;i++)
        A[i][0]=A[i][m+1]=-1;
    for(j=0;j<=m+1;j++)
        A[0][j]=A[n+1][j]=-1;
    A[l][c]=1;
    Q.push(make_pair(l,c));
    while(!Q.empty())
    {
        x=Q.front().first;
        y=Q.front().second;
        for(i=0;i<8;i++)
            if(A[x+DI[i]][y+DJ[i]]==0)
            {
                Q.push(make_pair(x+DI[i],y+DJ[i]));
                A[x+DI[i]][y+DJ[i]]=A[x][y]+1;
            }
        Q.pop();
    }
}

int main()
{
    fi>>n>>m;
    for(i=1;i<=n;i++)
    {
        fi.get(c);
        for(j=1;j<=m;j++)
        {
            fi.get(c);
            switch(c)
            {
                case ' ': R[i][j]=J[i][j]=0; break;
                case 'X': R[i][j]=J[i][j]=-1; break;
                case 'R': xr=i,yr=j; J[i][j]=0; break;
                case 'J': xj=i,yj=j; R[i][j]=0;
            }
        }
    }
    lee(R,xr,yr);
    lee(J,xj,yj);
    for(i=1;i<=n;i++)
        for(j=1;j<=m;j++)
            if(R[i][j]==J[i][j]&&R[i][j]!=-1)
                if(R[i][j]<mini)
                {
                    mini=R[i][j];
                    xmin=i;
                    ymin=j;
                }
    fo<<mini<<' '<<xmin<<' '<<ymin;
    fi.close();
    fo.close();
    return 0;
}

///Sursa lui Cipri
/*#include <cstdio>
#include <queue>
using namespace std;
FILE *fi,*fo;
struct PUNCT
{
    int l,c;
};
queue<PUNCT> Q;
int M[101][101],R[101][101],J[101][101];
int lr,cr,lj,cj,i,j,n,m,pozi,pozj;
char c;
PUNCT p,pn;
int dl[]={-1,-1,0,1,1,1,0,-1};
int dc[]={0,1,1,1,0,-1,-1,-1};
int main()
{
    fi=fopen("rj.in","r");
    fo=fopen("rj.out","w");
    fscanf(fi,"%d%d%c",&n,&m,&c);
    for(i=1;i<=n;i++)
    {
        for(j=1;j<=m;j++)
        {
            fscanf(fi,"%c",&c);
            if(c=='X')
                M[i][j]=1;
            else
            if(c=='R')
            {
                lr=i;
                cr=j;
                M[i][j]=1;
            }
            else
            if(c=='J')
            {
                lj=i;
                cj=j;
                M[i][j]=1;
            }
        }
        fscanf(fi,"%c",&c);
    }
    p.l=lr;
    p.c=cr;
    Q.push(p);
    R[lr][cr]=1;
    while(!Q.empty())
    {
        p=Q.front();
        for(int d=0;d<=7;d++)
        {
            pn.l=p.l+dl[d];
            pn.c=p.c+dc[d];
            int l=pn.l,c=pn.c;
            if(l>=1&&c>=1&&l<=n&&c<=m&&R[l][c]==0&&M[l][c]==0)
            {
                R[pn.l][pn.c]=1+R[p.l][p.c];
                Q.push(pn);
            }
        }
        Q.pop();
    }
    p.l=lj;
    p.c=cj;
    Q.push(p);
    J[lj][cj]=1;
    while(!Q.empty())
    {
        p=Q.front();
        for(int d=0;d<=7;d++)
        {
            pn.l=p.l+dl[d];
            pn.c=p.c+dc[d];
            int l=pn.l,c=pn.c;
            if(l>=1&&c>=1&&l<=n&&c<=m&&J[l][c]==0&&M[l][c]==0)
            {
                J[pn.l][pn.c]=1+J[p.l][p.c];
                Q.push(pn);
            }
        }
        Q.pop();
    }
    int min1=2000000;
    for(i=1;i<=n;i++)
        for(j=1;j<=m;j++)
            if(R[i][j]>0 && R[i][j]==J[i][j] && R[i][j]<min1)
            {
                pozi=i;
                pozj=j;
                min1=R[i][j];
            }
    fprintf(fo,"%d %d %d",min1,pozi,pozj);
    fclose(fi);
    fclose(fo);
    return 0;
}*/