Cod sursa(job #1620704)

Utilizator mihaiperjuMihai Perju mihaiperju Data 29 februarie 2016 12:06:06
Problema Rj Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.41 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;
                t[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]!=-1)
            {
                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<<tmin<<" "<<cx<<" "<<cy<<" "<<endl;

    return 0;
}