Cod sursa(job #2009612)

Utilizator Daria09Florea Daria Daria09 Data 10 august 2017 10:29:27
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.4 kb
#include <iostream>
#include <fstream>
#define NMAX 101
using namespace std;
ifstream f("rj.in");
ofstream g("rj.out");
short int n,m,a[NMAX][NMAX],sol[NMAX][NMAX],viz[NMAX][NMAX],sol2[NMAX][NMAX];
char s[102];
short int jx,jy,rx,ry,dx[]={-1,-1,-1,0,1,1,1,0},dy[]={-1,0,1,1,1,0,-1,-1};
struct rj
{
   short  int x,y;
}c[100*100];
void read()
{
    f>>n>>m; f.get();char c;
    for(int i=1;i<=n;i++)
    {
        f.getline(s,101);
        for(int j=0;j<m;j++)
        {
            if(s[j]=='X') a[i][j+1]=-1;
            if(s[j]=='R') { a[i][j+1]=1; rx=i; ry=j+1; }
            if(s[j]=='J'){ a[i][j+1]=2; jx=i; jy=j+1; }
        }
    }
    f.close();
}
void bordare()
{
    for(int i=0;i<=n+1;i++)
    {
        viz[i][0]=-1;
        viz[i][m+1]=-1;
    }
    for(int j=0;j<=m+1;j++)
    {
        viz[0][j]=-1;
        viz[n+1][j]=-1;
    }
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
    {
        sol[i][j]=-1;
        sol2[i][j]=-1;
    }
}
void lee_julieta()
{
    viz[jx][jy]=1;
    sol[jx][jy]=1;
    c[1].x=jx; c[1].y=jy;
    int p,u; u=p=1;
    while(p<=u)
    {
        int x=c[p].x,y=c[p].y;
        for(int i=0;i<8;i++)
            if(viz[x+dx[i]][y+dy[i]]==0&&a[x+dx[i]][y+dy[i]]!=-1&&viz[x+dx[i]][y+dy[i]]!=-1)
        {
            c[++u].x=x+dx[i];
            c[u].y=y+dy[i];
            viz[x+dx[i]][y+dy[i]]=1;
            sol[x+dx[i]][y+dy[i]]=sol[x][y]+1;
        }
        p++;
    }
}
void lee_romeo()
{
    viz[rx][ry]=2;
    sol2[rx][ry]=1;
    c[1].x=rx; c[1].y=ry;
    int p,u; u=p=1;
    while(p<=u)
    {
        int x=c[p].x,y=c[p].y;
        for(int i=0;i<8;i++)
            if(viz[x+dx[i]][y+dy[i]]!=2&&a[x+dx[i]][y+dy[i]]!=-1&&viz[x+dx[i]][y+dy[i]]!=-1)
        {
            c[++u].x=x+dx[i];
            c[u].y=y+dy[i];
            viz[x+dx[i]][y+dy[i]]=2;
            sol2[x+dx[i]][y+dy[i]]=sol2[x][y]+1;
        }
        p++;
    }
}
void solve()
{
    lee_julieta();
    lee_romeo();
    int solx=1,soly=1,ans=100*100+1;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
        if(max(sol[i][j],sol2[i][j])<ans&&a[i][j]!=-1&&sol[i][j]!=-1&&sol2[i][j]!=-1&&sol[i][j]==sol2[i][j])
        {
            ans=max(sol[i][j],sol2[i][j]);
            solx=i; soly=j;
        }
    g<<ans<<" "<<solx<<" "<<soly;
    g.close();
}
int main()
{
    read();
    bordare();
    solve();
    return 0;
}