Cod sursa(job #880430)

Utilizator alexclpAlexandru Clapa alexclp Data 16 februarie 2013 19:12:49
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.22 kb
#include <stdio.h>
#include <queue>

#define N 106

struct Pozitie {
    int x;
    int y;
};

using namespace std;

int n, m;
queue <Pozitie> coada;

int drumRomeo[N][N];
int drumJulieta[N][N];

int diri[] = {-1, -1, 0, 1, 1, 1, 0, -1};
int dirj[] = {0, 1, 1, 1, 0, -1 , -1, -1};

char map[N][N];

void bordeaza()
{
    for (int i = 0; i <= n; i++)
        map[i][0] = map[i][m] = 'X';
    for (int j = 0; j <= m; j++)
        map[0][j] = map[n+1][j] = 'X';

}

void lee(int drum[N][N], char personaj)
{

    Pozitie start;
    bool found = false;

    for (int i = 1; i <= n; i++) {

        for (int j = 1; j <= m; j++) {
            if (map[i][j] == personaj) {
                start.x = i;
                start.y = j;
                found = true;
                break;
            }
        }
        if (found) {
            break;
        }
    }

    coada.push(start);
    drum[start.x][start.y] = 1;

    while (!coada.empty()) {
        Pozitie curent = coada.front();
        coada.pop();

        for (int i = 0; i < 8; i++) {
            int x = curent.x + diri[i];
            int y = curent.y + dirj[i];
            if (drum[x][y] == 0 &&
                map[x][y] != 'X') {
                    drum[x][y] = drum[curent.x][curent.y] + 1;
                    coada.push((Pozitie){x,y});
                }
        }
    }
}

void cautaDrumMinim()
{
   int min = 9999;

    Pozitie pozitieIntalnire;

    for (int i = 1; i <= n; i ++) {
        for (int j = 1; j <= m; j++) {
            if (drumRomeo[i][j] == drumJulieta[i][j] &&
                drumRomeo[i][j] < min &&
                drumRomeo[i][j] != 0) {
                    min = drumRomeo[i][j];
                    pozitieIntalnire.x = i;
                    pozitieIntalnire.y = j;
                }
        }
    }

    printf("%d %d %d\n", min, pozitieIntalnire.x, pozitieIntalnire.y);
}

int main()
{
    freopen ("rj.in", "r", stdin);
    freopen ("rj.out", "w", stdout);

    scanf ("%d %d\n", &n, &m);

    for (int i = 1; i <= n; i++){
        gets(1 + map[i]);
    }

    bordeaza();
    lee(drumRomeo, 'R');
    lee(drumJulieta, 'J');

    cautaDrumMinim();



    return 0;
}