Cod sursa(job #2194578)

Utilizator Mirela_MagdalenaCatrina Mirela Mirela_Magdalena Data 13 aprilie 2018 19:28:36
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.16 kb
#include <cstdio>
#include <queue>
using namespace std;

queue <pair<int, int> >Q;
int ri, rj, ji, jj;
int a[260][260];
int b[260][260];
int n, m;
char c;
char u[260];
int vi[8]={-1, -1, 0, 1, 1, 1, 0, -1};
int vj[8]={0, -1, -1, -1, 0, 1, 1, 1};

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

int lee(int a[260][260], int pi, int pj)
{
    a[pi][pj] = 1;
    Q.push(make_pair(pi, pj));
    while(!Q.empty())
    {
        int i=Q.front().first, j=Q.front().second;
        Q.pop();
        for(int v=0; v<8; v++)
        {
            int iv=i+vi[v];
            int jv=j+vj[v];
            if(a[iv][jv] == 0)
            {
                Q.push(make_pair(iv, jv));
                a[iv][jv] = a[i][j]+1;
            }
        }
    }
}

int vmin = 100000, vx, vy;
void unire()
{
    for(int i=1; i<=n; i++)
        for(int j=1; j<=m; j++)
            if(a[i][j] == b[i][j] && a[i][j] != -1 && a[i][j] != 0)
            {
                if(a[i][j] < vmin)
                {
                    vmin = a[i][j];
                    vx = i;
                    vy = j;
                }
            }
    printf("%d %d %d", vmin, vx, vy);
}

int main()
{
    FILE *f=fopen("rj.in", "r");
    freopen("rj.out", "w", stdout);
    fscanf(f, "%d %d\n", &n, &m);
    bordare();
    for(int i=1; i<=n; i++)
    {
        fgets(u, 260, f);
        for(int j=0; j<m; j++)
        {
            if(u[j] == 'X')
            {
                a[i][j+1] = -1;
                b[i][j+1] = -1;
            }
            if(u[j] == 'R')
            {
                ri = i;
                rj = j+1;
                b[i][j+1] = -1;
            }
            if(u[j] == 'J')
            {
                ji = i;
                jj = j+1;
                a[i][j+1] = -1;
            }
        }
    }

    lee(a, ri, rj);
    lee(b, ji, jj);



    unire();

    return 0;
}