Cod sursa(job #1349547)

Utilizator IonSebastianIon Sebastian IonSebastian Data 20 februarie 2015 12:05:03
Problema Rj Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.01 kb
#include <cstdio>
#include <queue>
using namespace std;

const int MAX_N = 100, MAX_M = 100;
const int dlin[] = {-1,-1,-1,0,0,1,1,1};
const int dcol[] = {-1,0,1,-1,1,-1,0,1};

FILE *in, *out;

int a[MAX_N+2][MAX_M+2], romeo[MAX_N+2][MAX_M+2], julieta[MAX_N+2][MAX_M+2];
bool viz[MAX_N+2][MAX_M+2];
int n, m;

inline int minim(int a, int b)
{
    return (a<b)?a:b;
}

struct poz {
    int lin, col;
};

queue<poz> q;

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

void rlee()
{
    poz x, y;
    int i;
    while(!q.empty())
    {
        x = q.front();
        q.pop();
        viz[x.lin][x.col] = true;
        for(i = 0; i < 8; i++)
        {
            y.lin = x.lin + dlin[i];
            y.col = x.col + dcol[i];
            if(a[y.lin][y.col] != -1 && !viz[y.lin][y.col])
            {
                q.push(y);
                romeo[y.lin][y.col] = romeo[x.lin][x.col]+1;
                viz[y.lin][y.col] = true;
            }
        }
    }
}

void jlee()
{
    poz x, y;
    int i;
    while(!q.empty())
    {
        x = q.front();
        q.pop();
        viz[x.lin][x.col] = false;
        for(i = 0; i < 8; i++)
        {
            y.lin = x.lin + dlin[i];
            y.col = x.col + dcol[i];
            if(a[y.lin][y.col] != -1 && viz[y.lin][y.col])
            {
                q.push(y);
                julieta[y.lin][y.col] = julieta[x.lin][x.col]+1;
                viz[y.lin][y.col] = false;
            }
        }
    }
}

int main()
{
    in = fopen("rj.in", "r");
    out = fopen("rj.out", "w");
    fscanf(in, "%d%d", &n, &m);
    int i, j;
    char c;
    poz rom, jul;
    for(i = 1; i <= n; i++)
    {
        for(j = 1; j <= m; j++)
        {
            fscanf(in, "%c", &c);
            if(c == 'R')
            {
                rom.lin = i;
                rom.col = j;
                a[i][j] = 1;
            } else if(c == 'J') {
                jul.lin = i;
                jul.col = j;
                a[i][j] = 2;
            } else if(c == 'X') a[i][j] = -1;
        }
        if(fscanf(in,"\n"));
    }
    bordare();
    romeo[rom.lin][rom.col] = 1;
    julieta[jul.lin][jul.col] = 1;
    q.push(rom);
    rlee();
    q.push(jul);
    jlee();
    int tmin = n*m+1;
    int lin = n+1, col = m+1;
    for(i = 1; i <= n; i++)
        for(j = 1; j <= n; j++)
        {
            if((romeo[i][j] == julieta[i][j]) && (romeo[i][j] != 0))
            {
                if(tmin > romeo[i][j])
                {
                    tmin = romeo[i][j];
                    lin = i;
                    col = j;
                } else if(tmin == romeo[i][j])
                {
                    if(i < lin)
                    {
                        lin = i;
                        col = j;
                    } else if(i == lin)
                        col = minim(col,j);
                }
            }
        }
    fprintf(out, "%d %d %d", tmin, lin, col);
    fclose(in);
    fclose(out);
    return 0;
}