Cod sursa(job #1615837)

Utilizator AndreiFlorescuAndrei Florescu AndreiFlorescu Data 26 februarie 2016 21:38:31
Problema Rj Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.82 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> lee;
int mtr[102][102];

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

    int n, m, i, j;
    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' || c == 'J') {
                lee.push((poz){i, j});
                mtr[i][j] = -1;
            } else if (c == 'X') {
                mtr[i][j] = -1;
            }
        }
        //file_out << "\n";
    }

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

    // Calcularea solutiei
    // Lee
    while (!lee.empty()) {
        lact = lee.front().l;
        cact = lee.front().c;
        lee.pop();
        for (int i = 0; i < 8; i++) {
            lvec = lact + dl[i];
            cvec = cact + dc[i];
            if (mtr[lvec][cvec] == 0) {
                lee.push((poz){lvec, cvec});
                mtr[lvec][cvec] = mtr[lact][cact] + 1;
            } else if (mtr[lvec][cvec] != -1 && mtr[lvec][cvec] == mtr[lact][cact] + 1) {                                     // Afisarea solutiei
                file_out << mtr[lvec][cvec] << " " << lvec << " " << cvec;
                return 0;
            }
        }
    }

    return 0;
}