Cod sursa(job #1615869)

Utilizator AndreiFlorescuAndrei Florescu AndreiFlorescu Data 26 februarie 2016 21:54:08
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.9 kb
#include <iostream>
#include <fstream>
#include <queue>
#include <stdio.h>
#include <string>

using namespace std;

typedef struct {
    int l;
    int c;
} poz;

int dl[] = {0, -1, 0, 1, -1, -1, 1, 1};
int dc[] = {-1, 0, 1, 0, -1, 1, 1, -1};

queue <poz> leeR, leeJ;
int mtrR[102][102], mtrJ[102][102];

int main() {
    ifstream file_in ("rj.in");
    ofstream file_out ("rj.out");

    int n, m, i, j;
    int minim = 10001, soll, solc;
    int lact, cact, lvec, cvec;
    char c, sir[110], aux[5];

    // Citirea datelor
    file_in >> n >> m;
    file_in.getline(aux, 5);

    for (i = 1; i <= n; i++) {
        file_in.getline(sir, 107);
        for (j = 1; j <= m; j++) {
            c = sir[j - 1];
            //file_out << c << " ";
            if (c == 'R') {
                leeR.push((poz){i, j});
                mtrR[i][j] = 1;
            } else if (c == 'X') {
                mtrJ[i][j] = mtrR[i][j] = -1;
            } else if (c == 'J') {
                leeJ.push((poz){i, j});
                mtrJ[i][j] = 1;
            }
        }
        //file_out << "\n";
    }

    // Bordare
    for (int i = 0; i <= n + 1; i++) {
        mtrJ[i][0] = mtrJ[i][m + 1] = mtrR[i][0] = mtrR[i][m + 1] = -1;
    }
    for (int i = 0; i <= m + 1; i++) {
        mtrJ[0][i] = mtrJ[n + 1][i] = mtrR[0][i] = mtrR[n + 1][i] = -1;
    }

    // Calcularea solutiei
    // Lee
    while (!leeR.empty()) {
        lact = leeR.front().l;
        cact = leeR.front().c;
        leeR.pop();
        for (int i = 0; i < 8; i++) {
            lvec = lact + dl[i];
            cvec = cact + dc[i];
            if (mtrR[lvec][cvec] == 0) {
                leeR.push((poz){lvec, cvec});
                mtrR[lvec][cvec] = mtrR[lact][cact] + 1;
            }
        }
    }

    /*for (i = 1; i <= n; i++) {
        for (j = 1; j <= m ; j++) {
            file_out << mtrR[i][j] << " ";
        }
        file_out << "\n";
    }*/

    while (!leeJ.empty()) {
        lact = leeJ.front().l;
        cact = leeJ.front().c;
        leeJ.pop();
        for (int i = 0; i < 8; i++) {
            lvec = lact + dl[i];
            cvec = cact + dc[i];
            if (mtrJ[lvec][cvec] == 0) {
                leeJ.push((poz){lvec, cvec});
                mtrJ[lvec][cvec] = mtrJ[lact][cact] + 1;
            }
        }
    }
    /*file_out << "\n";
    for (i = 1; i <= n; i++) {
        for (j = 1; j <= m ; j++) {
            file_out << mtrJ[i][j] << " ";
        }
        file_out << "\n";
    }*/

    for (i = 1; i <= n; i++) {
        for (j = 1; j <= m; j++) {
            if(mtrR[i][j] == mtrJ[i][j] && mtrR[i][j] != -1 && mtrR[i][j] != 0 && mtrR[i][j] < minim){
                minim = mtrR[i][j];
                soll = i;
                solc = j;
            }
        }
    }

    file_out << minim << " " << soll << " " << solc;

    return 0;
}