Cod sursa(job #1436974)

Utilizator calinalexandruAlexandru Calin calinalexandru Data 16 mai 2015 18:06:16
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.74 kb
#include <fstream>
#include <queue>
#include <cstring>
using namespace std;
ifstream in("rj.in");
ofstream out("rj.out");
char a[101][101];
int b[101][101],r[101][101],ju[101][101],mj[101][101],dmj[101][101];
int dx[] = {-1, 0, 1, 0, 1, 1, -1, -1};
int dy[] = {0, 1, 0, -1, 1, -1, 1, -1};
struct punct
{
    int x,y;
};
queue <punct> q;
void lee(int mat[101][101],punct pct,int drum[101][101])
{
    q.push(pct);
    while(!q.empty())
    {
        punct poz;
        poz=q.front();
        q.pop();
        mat[poz.x][poz.y]=1;
        for(int i=0; i<8; i++)
            if(drum[poz.x+dx[i]][poz.y+dy[i]]==0 && mat[poz.x+dx[i]][poz.y+dy[i]]==0 )
            {
                drum[poz.x+dx[i]][poz.y+dy[i]]=drum[poz.x][poz.y]+1;
                punct t;
                t.x=poz.x+dx[i];
                t.y=poz.y+dy[i];
                q.push(t);
                mat[t.x][t.y]=1;
            }
    }
}
int main()
{
    int n,m,i,j,min=30000,minx=30000,miny=30000;
    punct romeo,julieta;
    in>>n>>m;
    in.get();
    for(i=1; i<=n; i++)
    {
        in.getline(a[i]+1,101);
        for(j=1; j<=m; j++)
        {
            if(a[i][j]=='X')
            {
                b[i][j]=1;
                ju[i][j]=-1;
                dmj[i][j]=-1;
            }
            if(a[i][j]==' ') b[i][j]=0;
            if(a[i][j]=='R')
            {
                romeo.x=i;
                romeo.y=j;
            }
            if(a[i][j]=='J')
            {
                julieta.x=i;
                julieta.y=j;
            }
        }
    }
    for(i=0; i<=n+1; i++)
    {
        b[0][i]=1;
        b[n+1][i]=1;
    }
    for(i=0; i<=m; i++)
    {
        b[i][0]=1;
        b[i][m+1]=1;
    }
    for(i=0; i<=n+1; i++)
    {
        r[0][i]=1;
        r[n+1][i]=1;
        mj[0][i]=1;
        mj[n+1][i]=1;
    }
    for(i=0; i<=m; i++)
    {
        r[i][0]=1;
        r[i][m+1]=1;
        mj[i][0]=1;
        mj[i][m+1]=1;
    }
    for(i=0; i<=n+1; i++)
    {
        ju[0][i]=-1;
        ju[n+1][i]=-1;
    }
    for(i=0; i<=m; i++)
    {
        ju[i][0]=-1;
        ju[i][m+1]=-1;
    }
    for(i=0; i<=n+1; i++)
    {
        dmj[0][i]=-1;
        dmj[n+1][i]=-1;
    }
    for(i=0; i<=m; i++)
    {
        dmj[i][0]=-1;
        dmj[i][m+1]=-1;
    }
    lee(r,romeo,ju);
    lee(mj,julieta,dmj);
    for(i=1;i<=n;i++)
        for(j=1;j<=m;j++)
        {
            if(dmj[i][j]==ju[i][j] && dmj[i][j]!=-1 && dmj[i][j]!=0)
            {
                if(dmj[i][j]<min)
                {
                    min=dmj[i][j];
                    minx=i;
                    miny=j;
                }
            }
        }
    out<<min+1<<" "<<minx<<" "<<miny;
}