Cod sursa(job #1620658)

Utilizator mihaiperjuMihai Perju mihaiperju Data 29 februarie 2016 11:50:21
Problema Rj Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.27 kb
#include <iostream>
#include <fstream>
#include <queue>

using namespace std;

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


int n,m,a[103][103],t[103][103];
struct perechi
{
    int x;
    int y;
};
queue<perechi>c;
int dx[]={-1,-1,0,1,1,1,0,-1};
int dy[]={0,1,1,1,0,-1,-1,-1};
perechi julieta;
int cx,cy,tmin;


int main()
{
    tmin=10609;
    fin>>n>>m;
    fin.get();
    for(int i=1;i<=n;i++)
    {
        char aux[102]={'\0'};
        fin.getline(aux,101);
        for(int j=1;j<=m;j++)
        {
            if(aux[j-1]=='X')
                a[i][j]=-1;
            else
                if(aux[j-1]=='R')
            {
                perechi r;
                r.x=i;
                r.y=j;
                a[i][j]=1;
                c.push(r);
            }
            else
                if(aux[j-1]=='J')
                {
                    julieta.x=i;
                    julieta.y=j;
                    t[i][j]=1;

                }
        }
    }

    //bordare
    for(int i=0;i<=n+1;i++)
        a[i][0]=a[i][m+1]=t[i][0]=t[i][m+1]=-1;
    for(int j=0;j<=m+1;j++)
        a[0][j]=a[n+1][j]=t[0][j]=t[n+1][j]=-1;
    //sfarsit bordare

    while(!c.empty())
    {
        perechi b;
        b=c.front();
        c.pop();

        for(int k=0;k<8;k++)
        {
            perechi z;
            z.x=b.x+dx[k];
            z.y=b.y+dy[k];
            if(!a[z.x][z.y])
            {
                a[z.x][z.y]=a[b.x][b.y]+1;
                c.push(z);
            }
        }
    }

    c.push(julieta);
    while(!c.empty())
    {
        perechi b;
        b=c.front();
        c.pop();

        for(int k=0;k<8;k++)
        {
            perechi z;
            z.x=b.x+dx[k];
            z.y=b.y+dy[k];

            if(!t[z.x][z.y])
            {
                t[z.x][z.y]=t[b.x][b.y]+1;
                c.push(z);

                if(t[z.x][z.y]==a[z.x][z.y])
                {
                    if(t[z.x][z.y]<tmin)
                    {
                        tmin=t[z.x][z.y];
                        cx=z.x;
                        cy=z.y;
                    }

                }
            }
        }
    }


    fout<<cx<<" "<<cy<<" "<<tmin<<endl;

    return 0;
}