Cod sursa(job #2425694)

Utilizator cyber_ghSoltan Gheorghe cyber_gh Data 24 mai 2019 23:39:43
Problema Rj Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.28 kb
#include <bits/stdc++.h>
 
using namespace std;


const int MAXN = 110;
 

bool MAT[MAXN][MAXN];
int DIST[2][MAXN][MAXN];
 
int N , M;
 
	
    int dx[] = {1,1,0,-1,-1,-1,0,1 };
    int dy[] = {0,-1,-1,-1, 0,-1, 1,1};

void solve (pair < int , int > start , int tip){
    
    queue <pair < int , int > > Q;
    Q.push(start);
    DIST[tip][start.first][start.second] = 0;
    
    while (!Q.empty()){
        pair < int,int > current = Q.front();
        Q.pop();
        //cout << current.first << " " << current.second << endl;
        for (int i = 0;i < 8;i++){ 
            int nextX = current.first +  dx[i];
            int nextY = current.second + dy[i];
            if (nextX < 1 || nextY < 1 || nextX > N || nextY > M ){
                continue;
            }

            if (MAT[nextX][nextY] == true) {
                continue ;
            } 
            if (DIST[tip][nextX][nextY] <= DIST[tip][current.first][current.second] + 1){
                continue;
            }
            DIST[tip][nextX][nextY] = DIST[tip][current.first][current.second] + 1;
            Q.push({nextX,nextY});
        }
        //cout << endl;
    }

    // for (int i = 1; i <= N;i++)
    //     for (int j = 1; j <= M;j++)
    //         cout << DIST[tip][i][j] << " \n"[j==M];

    // cout << endl;
}
 

pair < int,int > J,R;
    

int main(){
     
    ifstream fin("rj.in");
    ofstream fout("rj.out");
    fin >> N >> M;
    
    string tmp;
    getline(fin,tmp);
    


    for (int i = 1;i <= N;i++){
        getline(fin, tmp);
        for (int j = 0;j < M;j++){
            if (tmp[j] == 'R'){
                R = {i,j+1};
            }
            if (tmp[j] == 'J'){
                J = {i,j+1};
            }
            if (tmp[j] == 'X'){
                MAT[i][j+1] = true;
            }
            DIST[0][i][j+1] = 1e9;
            DIST[1][i][j+1] = 1e9;
        }
    }

  


    
    solve(J, 0);
    solve(R, 1);
    

    
    int MIN = 1e9;
    pair <int,int> minIndex;
    
    for (int i = 1;i <= N;i++){
        for (int j = 1;j <= M;j++){
            if (DIST[0][i][j] == DIST[1][i][j] && MIN > DIST[0][i][j]){
                MIN = DIST[0][i][j];
                minIndex = {i,j};
            }
        }
    }
    
    fout << MIN + 1 << " " << minIndex.first << " " <<minIndex.second;
    
    return 0;
}