Cod sursa(job #2513306)

Utilizator WilIiamperWilliam Damian Balint WilIiamper Data 22 decembrie 2019 20:38:41
Problema Rj Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.32 kb
#include <fstream>
#define MAX 105

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

int n, m, a[MAX][MAX], r[MAX][MAX], ju[MAX][MAX], ri, rj, ji, jj, minim;

int di[] = {-1, -1, 0, 1, 1, 1, 0, -1};
int dj[] = {0, 1, 1, 1, 0, -1, -1, -1};

int qi[MAX*MAX], sti, sfi;
int qj[MAX*MAX], stj, sfj;

void popj() { stj++; }
void popi() { sti++; }
void pushj(int x) { qj[sfj++] = x;}
void pushi(int x) { qi[sfi++] = x;}

bool OK (int i, int j, int t) {

    if (i < 1 || j < 1 || i > n || j > m)
        return false;

    if (a[i][j] == 1)
        return false;

    if (t == 1 && r[i][j])
        return false;
    else if (t == 2 && ju[i][j])
        return false;

    return true;
}

void bfs (int t) {
    int x, y, yy, xx;
    while (sti != sfi) {
        x = qi[sti];
        y = qj[stj];
        for (int l = 0; l < 8; l++) {
            xx = x + di[l];
            yy = y + dj[l];
            if ( OK(xx, yy, t) ) {
                pushi(xx);
                pushj(yy);
                if (t == 1)
                    r[xx][yy] = r[x][y]+1;
                else
                    ju[xx][yy] = ju[x][y] + 1;
            }
        }
        popi();
        popj();
    }
}

int main()
{

    int i, j;
    char x[MAX];
    fin >> n >> m;
    fin.getline (x, MAX);
    for (i = 1; i <= n; i++) {
        fin.getline(x, MAX);
        for (j = 0; j < m; j++) {
            if (x[j] == 'R') {
                a[i][j+1] = -2;
                ri = i;
                rj = j+1;
            }
            else if (x[j] == 'J') {
                a[i][j+1] = -3;
                ji = i;
                jj = j+1;
            }
            else if (x[j] == 'X')
                a[i][j+1] = 1;
        }
    }

    pushi(ri); pushj(rj);
    r[ri][rj] = 1;
    bfs(1);

    sti = 0; stj = 0; sfi = 0; sfj = 0;
    pushi(ji); pushj(jj);
    ju[ji][jj] = 1;
    bfs(2);

    minim = MAX * MAX;
    for (i = 1; i <= n; i++) {
        for (j = 1; j <= m; j++) {
            if (r[i][j] == ju[i][j] && r[i][j] > 0) {
                if (minim > r[i][j]) {
                    minim = r[i][j];
                    ri = i;
                    rj = j;
                }
            }
        }
    }

    fout << minim << " " << ri << " " << rj;
    return 0;
}