Cod sursa(job #1579543)

Utilizator PaulStighiStiegelbauer Paul-Alexandru PaulStighi Data 24 ianuarie 2016 20:53:55
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.39 kb
#include<fstream>
#include<climits>
#include<cstring>
#include<queue>
using namespace std;
ifstream fin("rj.in");
ofstream fout("rj.out");

int N,M,Solx,Soly,Tmin = INT_MAX;
int A1[128][128],A2[128][128];
char L[128];
int dx[]={-1,0,1,1,1,0,-1,-1};
int dy[]={1,1,1,0,-1,-1,-1,0};

queue < pair<int,int> > Q1,Q2;

void Read()
{
    fin>>N>>M;

    fin.get();

    for(int i=1;i<=N;++i)
    {
        fin.getline(L,128);
        for(int j=0;j<M;++j)
        {
            if(L[j] == 'X')  A1[i][j+1] = A2[i][j+1] = -1;
            else
                if(L[j] == 'R')
                {
                    Q1.push(make_pair(i,j+1));
                    A1[i][j+1] = 1;
                }
                else
                    if(L[j] == 'J')
                    {
                        Q2.push(make_pair(i,j+1));
                        A2[i][j+1] = 1;
                    }
        }
    }
}

void Lee()
{
    for(int i = 0; i <= N+1; i++)
        A1[i][0] = A1[i][M+1] = A2[i][0] = A2[i][M+1] = -1;
    for(int i = 0; i <= M+1; i++)
        A1[0][i] = A1[N+1][i] = A2[0][i] = A2[N+1][i] = -1;

    while(!Q1.empty())
    {
        int X=Q1.front().first;
        int Y=Q1.front().second;
        Q1.pop();

        for(int j=0;j<8;j++)
        {
            int XNew = X + dx[j];
            int YNew = Y + dy[j];

            if(A1[XNew][YNew] == 0)
            {
                A1[XNew][YNew] = A1[X][Y] + 1;
                Q1.push(make_pair(XNew,YNew));
            }
        }
    }

    while(!Q2.empty())
    {
        int X=Q2.front().first;
        int Y=Q2.front().second;
        Q2.pop();

        for(int j=0;j<8;j++)
        {
            int XNew = X + dx[j];
            int YNew = Y + dy[j];

            if(A2[XNew][YNew] == 0)
            {
                A2[XNew][YNew] = A2[X][Y] + 1;
                Q2.push(make_pair(XNew,YNew));
            }
        }
    }

    for(int i=1;i<=N;i++)
    {
        for(int j=1;j<=M;j++)
        {
            if(A1[i][j] == A2[i][j] && A1[i][j] > 0 && A1[i][j] < Tmin)
            {
                Tmin = A1[i][j];
                Solx = i;
                Soly = j;
            }
        }
    }
}

void Print()
{
    fout<<Tmin<<" "<<Solx<<" "<<Soly<<"\n";
}

int main()
{
    Read();
    Lee();
    Print();

    fin.close();
    fout.close();
    return 0;
}