Cod sursa(job #2425652)

Utilizator cyber_ghSoltan Gheorghe cyber_gh Data 24 mai 2019 22:46:31
Problema Rj Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.84 kb
#include <bits/stdc++.h>

using namespace std;

const int MAXN = 110;
int N, M;

int MAT[MAXN][MAXN];

int DR[MAXN][MAXN], DJ[MAXN][MAXN];

pair<int,int> ROMEO, JULIET;

const int MAX_VAL = 10;

bool isValid(pair<int,int> pos) {
    if (pos.first >= 1 && pos.first <= N && 
    pos.second <= M && pos.second >= 1 && MAT[pos.first][pos.second] != MAX_VAL) return true;
    return false;
}

pair<int,int> start;
pair<int,int> finish;

void bfs(pair<int,int> start, int dist[MAXN][MAXN]){
    int dx[] = {1,1,0,-1,-1,-1,0,1 };
    int dy[] = {0,-1,-1,-1, 0,-1, 1,1};

    queue<pair<int,int> > Q;
    Q.push(start);
    dist[start.first][start.second] = 0;
    while (!Q.empty()) {

        pair<int,int> curr = Q.front();
        Q.pop();
        for (int k = 0 ; k < 8;k++){
            int nextX = curr.first + dx[k];
            int nextY = curr.second + dy[k];
            //cout << nextX << " " << nextY << endl;
            if (isValid({nextX, nextY})) {
                if (dist[nextX][nextY] == 0) {
                    dist[nextX][nextY] = dist[curr.first][curr.second] + 1;
                    Q.push({nextX, nextY});
                } else if (dist[curr.first][curr.second] + 1 < dist[nextX][nextY]) {
                    dist[nextX][nextY] = dist[curr.first][curr.second] + 1;
                }
            } 
        }
    }

    dist[start.first][start.second] = 0;
    for (int i = 1; i <= N;i++)
        for (int j = 1; j <= M; j++) {
            if( dist[i][j] == MAX_VAL) dist[i][j] = 0;
            cout << dist[i][j] << " \n"[j==M];
        }
    cout << endl;
}

int main () {
    ifstream fin("rj.in");
    ofstream cout("rj.out");


    fin >> N>> M;
    //fin.get();
    for (int i = 0; i <= N;i++) {
        string tmp;
        getline(fin, tmp);
        for (int j = 0; j < tmp.size();j++)  {
            switch (tmp[j]){
            case 'R':
                start = {i, j + 1};
                MAT[i][j + 1] = 2;
                break;
            case 'J':
                finish = {i, j + 1};
                MAT[i][j + 1] = 3;
                break;
            case 'X':
                MAT[i][j + 1] = DJ[i][j + 1] = DR[i][j + 1] =  MAX_VAL;
            
            default:
                break;
            }
        }
    }
    bfs(start, DR);
    bfs(finish, DJ);

    int minVal = MAX_VAL;
    pair<int,int> minIndex;
    for (int i = 1; i <= N;i++)
        for(int j = 1; j <= M;j++) {
            if (DJ[i][j] != 0 && DR[i][j] != 0)
                if (max(DJ[i][j], DR[i][j]) < minVal && DJ[i][j] == DR[i][j]) {
                    minVal = max(DJ[i][j], DR[i][j]);
                    minIndex = {i,j};
                } 
                //minVal = min(minVal, DJ[i][j] + DR[i][j]);

        }

    int i = minIndex.first, j = minIndex.second;
    cout << min(DJ[i][j], DR[i][j]) + 1<<" ";
    cout << minIndex.first << " " << minIndex.second;
    
    return 0;
}