Cod sursa(job #1369389)

Utilizator DobosDobos Paul Dobos Data 3 martie 2015 00:25:12
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.56 kb
#include <iostream>
#include <fstream>
#include <deque>
#include <string>
#include <cmath>
const int dx[] {0,0,-1,1,-1,-1,1,1};
const int dy[] {1,-1,0,0,-1,1,1,-1};
using namespace std;
ifstream f("rj.in");
ofstream g("rj.out");
deque <int> lyr,lxr,lxj,lyj;
int r[105][105],ju[105][105],n,m;

void afis()
{
    int i,j;
    for(i = 1; i <= n; i++)
    {
        for(j = 1; j <= m; j++)
            g<<r[i][j]<<" ";
        g<<"\n";
    }
}

void leej( )
{
    int ux,uy,xx,yy,i;
    while(!lxj.empty())
    {
        xx=lxj.front();
        yy=lyj.front();
        for(i = 0 ; i < 8 ; i++)
        {
            ux = xx + dx[i];
            uy = yy + dy[i];
            if(ju[ux][uy] == 0)
            {
                ju[ux][uy] = ju[xx][yy] +1;
                lxj.push_back(ux);
                lyj.push_back(uy);
            }
        }
        lxj.pop_front();
        lyj.pop_front();
    }
}
void leer( )
{
    int ux,uy,xx,yy,i;
    while(!lxr.empty())
    {
        xx=lxr.front();
        yy=lyr.front();
        for(i = 0 ; i < 8 ; i++)
        {
            ux = xx + dx[i];
            uy = yy + dy[i];
            if(r[ux][uy] == 0)
            {
                r[ux][uy] = r[xx][yy] +1;
                lxr.push_back(ux);
                lyr.push_back(uy);
            }
        }
        lxr.pop_front();
        lyr.pop_front();
    }
}


int main()
{
    int i,j,ym,xm,mn=1e9;
    char x;
    f>>n>>m;
    f.get(x);
    for(i = 1; i <= n ; i++)
    {
        j=0;
        while(f.get(x) && x != '\n')
        {
            j++;
            if(x == ' ')
                r[i][j]=ju[i][j]=0;
            if(x == 'X')
                r[i][j]=ju[i][j]=-1;
            if(x == 'R')
            {
                lxr.push_back(i);
                lyr.push_back(j);
                r[i][j] = 1;
            }
            if(x == 'J')
            {
                lxj.push_back(i);
                lyj.push_back(j);
                ju[i][j] = 1;
            }
        }
        for(int k=j+1; k <= m; k++)
            r[i][k]=ju[i][k]=0;
    }
    for(i = 0; i <= n+1; i++)
        r[i][0]=ju[i][0]=r[i][m+1]=ju[i][m+1]=-1;
    for(i = 0; i <= m+1; i++)
        r[0][i]=ju[0][i]=r[n+1][i]=ju[n+1][i]=-1;
        leej();
        leer();

        for(i = 1; i <= n; i++)
        for(j = 1; j <= m; j++)
            if(r[i][j] == ju[i][j] && r[i][j] < mn && r[i][j]!= -1 && r[i][j] != 0)
                mn=r[i][j],ym=j,xm=i;

      g<<mn<<" "<<xm<<" "<<ym;

 //   afis();

    return 0;
}