Cod sursa(job #1366916)

Utilizator trust2014Alex Murariu trust2014 Data 1 martie 2015 14:42:43
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.56 kb
#include <iostream>
#include <fstream>
#include <deque>


using namespace std;
ifstream f("rj.in");
ofstream g("rj.out");
int R[180][180],J[180][180];
const int dx[] = {-1, 0, 1, 0, -1,-1, 1, 1};
const int dy[] = {0, 1, 0, -1, -1, 1, 1, -1};
deque < int > qx,qy;
void afisare(int n,int m)
{
    int x,y;
    int timp=1e9;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
          if(R[i][j]==J[i][j]&&R[i][j]!=-1)
          {
            if(R[i][j]<timp&&R[i][j]!=0)
            {
            timp=R[i][j];
            x=i;
            y=j;
            }
          }
        }
    }
    g<<timp<<" "<<x<<" "<<y;
}

void Romeo()
{
    int nx,ny,yy,xx;
    while(!qx.empty())
        {
        xx = qx.front();
        yy = qy.front();
        qx.pop_front();
        qy.pop_front();
        for(int i = 0; i < 8; i++)
            {
            nx = xx + dx[i];
            ny = yy + dy[i];
            if(R[nx][ny] == 0)
            {
                R[nx][ny] = R[xx][yy] + 1;
                qx.push_back(nx);
                qy.push_back(ny);

            }
        }

    }
}
void Julieta()
{
    int nx,ny,yy,xx;
    while(!qx.empty())
        {
        xx = qx.front();
        yy = qy.front();
        qx.pop_front();
        qy.pop_front();
        for(int i = 0; i < 8; i++)
            {
            nx = xx + dx[i];
            ny = yy + dy[i];
            if(J[nx][ny] == 0)
            {
                J[nx][ny] = J[xx][yy] + 1;
                qx.push_back(nx);
                qy.push_back(ny);

            }
        }

    }
}



int main()
{
    int N,M,XR,YR,XJ,YJ;
    char o;
    f >> N >> M;
    f.get(o);
    for(int i = 1; i <= N; i++){
        for(int j = 1; j <= M + 1; j++)
        {
                f.get(o);
            if(o == 'X')
                R[i][j] = J[i][j] = -1;
            if(o == 'R')
            {
                XR = i;
                YR = j;
                R[XR][YR] = 1;
            }
            if(o == 'J')
            {
                XJ = i;
                YJ = j;
                J[XJ][YJ] = 1;
            }
            if(o == '\n')
                j = 32000;
        }
    }
    for(int i = 0; i <= M + 1; i++)
        R[0][i] = R[N+1][i] = J[0][i] = J[N+1][i] = -1;
    for(int i = 0; i <= N + 1; i++)
        R[i][0] = R[i][M+1] = J[i][0] = J[i][M+1] = -1;
    qx.push_back(XR);
    qy.push_back(YR);
    Romeo();
    qx.push_back(XJ);
    qy.push_back(YJ);
    Julieta();
    afisare(N,M);
    return 0;
}