Cod sursa(job #653706)

Utilizator alexalbu95Albu Alexandru alexalbu95 Data 28 decembrie 2011 17:39:57
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.84 kb
#include <fstream>
#include <cstring>
#include <iomanip>
using namespace std;

const int maxn=110;
const int Maxn=11000;
ifstream f("rj.in");
ofstream g("rj.out");

int n, m, a[maxn][maxn], b[maxn][maxn], xj, yj, xr, yr;
char s[maxn];
struct point
{
    int x, y;
} v[Maxn];

int dx[]={-1, -1, 0, 1, 1, 1, 0, -1};
int dy[]={0, 1, 1, 1, 0, -1, -1, -1};

void read();
void bordare();
void lee1(int, int);
void lee2(int, int);
void rasp();

int main()
{
    read();
    bordare();
    lee1(xj, yj);
    lee2(xr, yr);
    rasp();
}

void read()
{
    int i, j;

    f>>n>>m;
    f.get();
    for(i=1; i<=n; ++i)
    {
        f.getline(s, maxn);

        for(j=0; j<m; ++j)
        {
            if(s[j]=='X') b[i][j+1]=a[i][j+1]=-2;
            else if(s[j]=='J')
                 {
                     b[i][j+1]=a[i][j+1]=-1;
                     xj=i;
                     yj=j+1;
                 }
                 else if(s[j]=='R')
                      {
                           b[i][j+1]=a[i][j+1]=-1;
                           xr=i;
                           yr=j+1;
                      }
        }
    }
}

void bordare()
{
    for(int i=0; i<=n+1; ++i) b[i][0]=b[i][m+1]=a[i][0]=a[i][m+1]=-2;
    for(int i=0; i<=m+1; ++i) b[0][i]=b[n+1][i]=a[0][i]=a[n+1][i]=-2;
}


void lee1(int pi, int pj)
{
    int i, j, inou, jnou, k, s, d;

    v[1].x=pi;
    v[1].y=pj;
    s=d=1;

    while(s<=d)
    {
        i=v[s].x;
        j=v[s].y;

        for(k=0; k<8; ++k)
        {
            inou=i+dx[k];
            jnou=j+dy[k];
            if(a[inou][jnou]==0 || a[inou][jnou]>(a[i][j]+2))
            {
                a[inou][jnou]=a[i][j]+2;
                v[++d].x=inou;
                v[d].y=jnou;
            }
        }
        ++s;
    }
}

void lee2(int pi, int pj)
{
    int i, j, inou, jnou, k, s, d;

    v[1].x=pi;
    v[1].y=pj;
    s=d=1;

    while(s<=d)
    {
        i=v[s].x;
        j=v[s].y;

        for(k=0; k<8; ++k)
        {
            inou=i+dx[k];
            jnou=j+dy[k];
            if(b[inou][jnou]==0 || b[inou][jnou]>(b[i][j]+2))
            {
                b[inou][jnou]=b[i][j]+2;
                v[++d].x=inou;
                v[d].y=jnou;
            }
        }
        ++s;
    }
}

void rasp()
{
    int i, j, maxim=Maxn, pozi, pozj;

    for(i=1; i<=n; ++i)
        for(j=1; j<=m; ++j)
        {
            if(a[i][j]==b[i][j] && a[i][j]>0 && a[i][j]<maxim)
            {
                maxim=a[i][j];
                pozi=i;
                pozj=j;
            }
            else if(a[i][j]==maxim && i<pozi)
                 {
                     maxim=a[i][j];
                     pozi=i;
                     pozj=j;
                 }
        }
    g<<(maxim+1)/2+1<<" "<<pozi<<" "<<pozj<<"\n";
}