Cod sursa(job #1592541)

Utilizator tudorgalatanRoman Tudor tudorgalatan Data 7 februarie 2016 18:51:06
Problema Rj Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.77 kb
#include <fstream>
#include <climits>
#define MAX 100

using namespace std;

ifstream fin  ("rj.in");
ofstream fout ("rj.out");

void read ();
void bordare ();
void Romeo ();
void Julieta ();
void solve ();
void print ();

unsigned short int N, M;
char s[MAX];

const short int dx[] = {-1, -1,  0,  1,  1,  1,  0, -1};
const short int dy[] = { 0,  1,  1,  1,  0, -1, -1, -1};
short int a[MAX][MAX], mat[MAX][MAX];
unsigned short int i, j, k, xr, yr, xj, yj;

int pr, ul, x, y, lin, col, tmin=INT_MAX;

int main ()
{
    read ();
    solve ();
    print ();
    return 0;
}

struct coord
{
    int x, y;
};
coord q[MAX];

void read ()
{
    fin >> N >> M;
    fin.get();
    for (i=1; i<=N; i++)
    {
        fin.getline(s,MAX);
        for (j=0; j<M; j++)
            if (s[j] == ' ')
                a[i][j+1] = 0;
            else if (s[j] == 'X')
                a[i][j+1] = 1;
            else if (s[j] == 'R')
            {
                xr = i;
                yr = j+1;
            }
            else
            {
                xj = i;
                yj = j+1;
            }
    }
    fin.close();
    for (i=1; i<=N; i++)
        for (j=1; j<=M; j++)
            mat[i][j] = a[i][j];
}

void solve ()
{
    bordare ();
    Romeo ();
    Julieta ();
}

void print ()
{
    for (i=1; i<=N; i++)
        for (j=1; j<=M; j++)
            if (a[i][j] == mat[i][j] && a[i][j]>1 && a[i][j]-1 < tmin)
            {
                tmin = a[i][j] - 1;
                lin = i;
                col = j;
            }
    fout << tmin << " " << lin << " " << col;
}

void bordare ()
{
    for (i=0; i<=N+1; i++)
        mat[i][0] = mat[i][M] = a[i][0] = a[i][M] = -1;
    for (i=0; i<=M+1; i++)
        mat[0][i] = mat[N][i] = a[0][i] = a[N][i] = -1;
}

void Romeo ()
{
    pr = ul = 0;
    a[xr][yr] = 2;
    q[ul].x = xr;
    q[ul].y = yr;
    while (pr <= ul)
    {
        i = q[pr].x;
        j = q[pr].y;
        pr++;
        for (k=0; k<8; k++)
        {
            x = i + dx[k];
            y = j + dy[k];
            if (a[x][y] == 0)
            {
                ul++;
                q[ul].x = x;
                q[ul].y = y;
                a[x][y] = a[i][j] + 1;
            }
        }
    }
}

void Julieta ()
{
    pr = ul = 0;
    mat[xj][yj] = 2;
    q[ul].x = xj;
    q[ul].y = yj;
    while (pr <= ul)
    {
        i = q[pr].x;
        j = q[pr].y;
        pr++;
        for (k=0; k<4; k++)
        {
            x = i + dx[k];
            y = j + dy[k];
            if (mat[x][y] == 0)
            {
                ul++;
                q[ul].x = x;
                q[ul].y = y;
                mat[x][y] = mat[i][j] + 1;
            }
        }
    }
}