Cod sursa(job #1579491)

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

int N,M,Solx,Soly,Tmin = 100005;
int A[128][128],Succ[128][128];
char L[128];
int dx[]={1,0,-1,0,1,1,-1,-1};
int dy[]={0,-1,0,1,1,-1,-1,1};

queue < pair<int,int> > Q;

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')  A[i][j+1] = -1;
            else
                if(L[j] == 'R')
                {
                    Q.push(make_pair(i,j+1));
                    A[i][j+1] = 0;
                    Succ[i][j+1]=1;
                }
                else
                    if(L[j] == 'J')
                    {
                        Q.push(make_pair(i,j+1));
                        A[i][j+1] = 0;
                        Succ[i][j+1]=2;
                    }
        }
    }
}

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

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

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

            if(A[XNew][YNew] == 0)
            {
                A[XNew][YNew] = A[X][Y] + 1;
                Succ[XNew][YNew] = Succ[X][Y];
                Q.push(make_pair(XNew,YNew));
            }
            else
                if(A[XNew][YNew] > 0 && (Succ[X][Y] != Succ[XNew][YNew]))
                {
                    if( (A[XNew][YNew]-1) < Tmin)
                    {
                        Solx=X; Soly=Y;
                        Tmin=A[XNew][YNew];
                    }
                }
        }
    }
}

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

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

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