Cod sursa(job #1634237)

Utilizator filip.mihalutMihalut Filip filip.mihalut Data 6 martie 2016 13:34:28
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.86 kb
#include <iostream>
#include <fstream>
#include <queue>
#define dim 103
#define inf 1e9

using namespace std;

ifstream f ("rj.in");
ofstream g ("rj.out");

queue < pair < unsigned short,unsigned short > > Q;

const short dl[]={-1,0,1,0,1,1,-1,-1};
const short dc[]={0,-1,0,1,1,-1,1,-1};

int n,m,romeo[dim][dim],julieta[dim][dim],i,Max = inf,j,pozi_r,pozj_r,pozi_j,pozj_j,l,c,nl,nc;
char sir[dim];

inline void lee(int a[dim][dim],int pozi,int pozj,int x,int y)
{
    a[pozi][pozj] = 1;
    Q.push(make_pair(pozi,pozj));
    while(!Q.empty())
    {
        l = Q.front().first;
        c = Q.front().second;
        Q.pop();
        for(i = 0;i <= 7;i++)
        {
            nl = dl[i] + l;
            nc = dc[i] + c;
            if(nl >= 1 && nc >= 1 && nl <= n && nc <= m && a[nl][nc] == 0)
            {
                a[nl][nc] = a[l][c] + 1;
                Q.push(make_pair(nl,nc));
            }
        }
        if(a[x][y] != 0)
            break;
    }
}

int main()
{
    f >> n >> m;
    for(i = 1;i <= n;i++)
    {
        f.get();
        f.get(sir,dim);
        for(j = 1;j <= m;j++)
        {
            if(sir[j - 1] == 'X')
                romeo[i][j] = -1,julieta[i][j] =-1;
            if(sir[j - 1] == 'R')
                pozi_r = i,pozj_r = j;
            if(sir[j - 1] == 'J')
                pozi_j = i,pozj_j = j;
        }
    }
    lee(romeo,pozi_r,pozj_r,pozi_j,pozj_j);
    while(!Q.empty())
        Q.pop();
    lee(julieta,pozi_j,pozj_j,pozi_r,pozj_r);
    for(i = 1;i <= n;i++)
    {
        for(j = 1;j <= m;j++)
            if(romeo[i][j] == julieta[i][j] && romeo[i][j] > 0 && Max > romeo[i][j])
            {
                Max = romeo[i][j];
                pozi_r = i;
                pozj_r = j;
            }
    }
    g << Max  <<" "<< pozi_r <<" " << pozj_r;
    return 0;
}