Cod sursa(job #808187)

Utilizator beldeabogdanBogdan Beldea beldeabogdan Data 6 noiembrie 2012 14:22:18
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.26 kb
#include <fstream>
#include <cstdio>
#include <queue>
#define NMax 105
using namespace std;

struct pozitie {
    int x,y;
};
pozitie pr,pj;
queue <pozitie> q;

int matr[NMax][NMax],matj[NMax][NMax];
int n,m;

void citire() {
    freopen("rj.in","r",stdin);
    char crt;
    scanf("%d %d",&n,&m);
    getchar();
    for (int y = 1;y<=n;y++) {
        for (int x = 1;x <= m;x++) {
            crt = getchar();
            switch (crt) {
                case 'R': {
                    matr[y][x] = 1;
                    pr.x = x;
                    pr.y = y;
                    break;
                }
                case 'J': {
                    matj[y][x] = 1;
                    pj.x = x;
                    pj.y = y;
                    break;
                }
                case 'X': {
                    matr[y][x] = matj[y][x] = -1;
                    break;
                }
            }
        }
        getchar();
    }
}

void bordare() {
    int x,y;
    for (x=0;x<=m+1;x++) matr[0][x] = matj[0][x] = matr[n+1][x] = matj[n+1][x] = -1;
    for (y=0;y<=n+1;y++) matr[y][0] = matj[y][0] = matr[y][m+1] = matj[y][m+1] = -1;
}

int dx[] = {0,-1,-1,-1,0,1,1,1,0};
int dy[] = {0,-1,0,1,1,1,0,-1,-1};

void lee(int y, int x,int mat[NMax][NMax]) {
    pozitie pos;
    for (int i = 1;i <= 8; i++) {
        if (mat[y+dy[i]][x+dx[i]] == 0) {
            mat[y+dy[i]][x+dx[i]] = mat[y][x] +1;
            pos.x = x+dx[i];
            pos.y = y+dy[i];
            q.push(pos);
        }
    }
}

int main () {
    pozitie pos;
    citire();
    bordare();
    pos = pr;
    q.push(pos);
    while (!q.empty()) {
        pos = q.front();
        q.pop();
        lee(pos.y,pos.x,matr);
    }
    pos = pj;
    q.push(pos);
    while (!q.empty()) {
        pos = q.front();
        q.pop();
        lee(pos.y,pos.x,matj);
    }
    int tmin = 2000000000;
    int x,y;
    for (y=1;y<=n;y++)
    for (x=1;x<=m;x++)
    if (matj[y][x] == matr[y][x] && matr[y][x] > 0) {
        if (matr[y][x] < tmin) {
            tmin = matr[y][x];
            pos.x = x;
            pos.y = y;
        }
    }
    ofstream out("rj.out");
    out << tmin << " " << pos.y << " " << pos.x << "\n";
    return 0;
}