Cod sursa(job #2150069)

Utilizator EclipseTepes Alexandru Eclipse Data 3 martie 2018 11:34:26
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.15 kb
#include <iostream>
#include <fstream>
#include <string.h>
#include <queue>
#include <climits>
#define dMAX 101

using namespace std;

unsigned short int n, m;
unsigned short int rOx, rOy, jOx, jOy;
unsigned short int new_x, new_y;
char matrix[dMAX][dMAX];
char tempC, tempString[dMAX];
unsigned int jMatrix[dMAX][dMAX];
unsigned int rMatrix[dMAX][dMAX];
unsigned int sMIN = INT_MAX, sOx, sOy;

bool st;

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

struct Position {
    unsigned short int x, y;
    bool juliet;
} pVerif, temp;

queue<Position> myQueue;

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

void PrintFMatrix() {
    for (unsigned short int i = 1; i <= n; i++) {
        for (unsigned short int j = 1; j <= m; j++) {
            cout << rMatrix[i][j] << " ";
        }
        cout << "\n";
    }
    cout << "\n";
}

int main()
{
    unsigned short int i, j;
    fin >> n >> m;
    fin.get();
    for (i = 1; i <= n; i++) {
        fin.getline(tempString, 101);
        for (j = 1; j <= m; j++) {
            matrix[i][j] = tempString[j - 1];
            if (matrix[i][j] == 'J') {
                jOx = i;
                jOy = j;
            } else if (matrix[i][j] == 'R') {
                rOx = i;
                rOy = j;
            }
        }
    }
    rMatrix[rOx][rOy] = 1;
    jMatrix[jOx][jOy] = 1;
    temp.x = rOx, temp.y = rOy;
    temp.juliet = false;
    myQueue.push(temp);
    temp.x = jOx, temp.y = jOy;
    temp.juliet = true;
    myQueue.push(temp);

    while (!myQueue.empty()) {

        pVerif = myQueue.front();

        for (i = 0; i < 8; i++) {
            new_x = pVerif.x + dx[i];
            new_y = pVerif.y + dy[i];
            if (new_x > 0 && new_y > 0 && new_x <= n && new_y <= m) {
                if (matrix[new_x][new_y] == ' ') {
                    if (pVerif.juliet == true) {
                        if (!jMatrix[new_x][new_y]) {
                            jMatrix[new_x][new_y] = jMatrix[pVerif.x][pVerif.y] + 1;
                            temp.x = new_x, temp.y = new_y;
                            temp.juliet = true;
                            myQueue.push(temp);
                        }
                    } else {
                        if (!rMatrix[new_x][new_y]) {
                            rMatrix[new_x][new_y] = rMatrix[pVerif.x][pVerif.y] + 1;
                            temp.x = new_x, temp.y = new_y;
                            temp.juliet = false;
                            myQueue.push(temp);
                        }
                    }
                }
            }
        }
        myQueue.pop();
    }
    for (i = 1; i <= n; i++) {
        for (j = 1; j <= m; j++) {
            if (matrix[i][j] == ' ' && jMatrix[i][j] && rMatrix[i][j]) {
                if (jMatrix[i][j] == rMatrix[i][j]) {
                    if (jMatrix[i][j] < sMIN) {
                        sMIN = jMatrix[i][j];
                        sOx = i, sOy = j;
                    }
                }
            }
        }
    }
    fout << sMIN << " " << sOx << " " << sOy;
    return 0;
}