Cod sursa(job #2194604)

Utilizator Hidden.bdBurlacu Doru Hidden.bd Data 13 aprilie 2018 20:31:03
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.43 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <cstring>
#include <queue>

using namespace std;

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

//#define fin cin
//#define fout cout

int n, m;
int R[102][102], J[102][102];
bool harta[102][102];

bool in( pair<int, int> a ){
    if( a.first >= 1 && a.first <= n && a.second >= 1 && a.second <= m ) return true;
    else return false;
}

int main(){
    
    
    int i1, j1, i2, j2;
    int di[] = { -1, 0, 1, 0, -1, 1, 1, -1}, dj[] = { 0, 1, 0, -1, 1, 1, -1, -1};
    queue<pair<int,int>> q;
    
    fin >> n >> m;
    
    string c;
    getline(fin, c);
    
    for( int i = 1 ; i <= n ; ++i ){
        string s;
        getline(fin, s);
        for( int j = 0 ; j < m ; ++j ){
            if( s[j] == 'X' ) harta[i][j+1] = 1;
            else harta[i][j+1] = 0;
            
            if( s[j] == 'R' ){
                i1 = i;
                j1 = j + 1;
            }else if( s[j] == 'J' ){
                i2 = i;
                j2 = j + 1;
            }
        }

    }
    
    pair<int, int> crr, nou;
    
    //R
    R[i1][j1] = 1;
    q.push(make_pair(i1, j1));
    
    while( !q.empty() ){
        crr = q.front();
        q.pop();
        
        for( int i = 0 ; i < 8 ; ++i ){
            nou.first = crr.first + di[i];
            nou.second = crr.second + dj[i];
            
            if( in(nou) && !harta[nou.first][nou.second] && !R[nou.first][nou.second] ){
                R[nou.first][nou.second] = R[crr.first][crr.second] + 1;
                q.push(nou);
            }
        }
    }
    
    //J
    J[i2][j2] = 1;
    q.push(make_pair(i2, j2));
    
    while( !q.empty() ){
        crr = q.front();
        q.pop();
        
        for( int i = 0 ; i < 8 ; ++i ){
            nou.first = crr.first + di[i];
            nou.second = crr.second + dj[i];
            
            if( in(nou) && !harta[nou.first][nou.second] && !J[nou.first][nou.second] ){
                J[nou.first][nou.second] = J[crr.first][crr.second] + 1;
                q.push(nou);
            }
        }
    }
    
    int minn = 10000;
    
    for( int i = 1 ; i <= n ; ++i ){
        for( int j = 1 ; j <= m ; ++j ){
            if( R[i][j] && J[i][j] && R[i][j] == J[i][j] && R[i][j] < minn ){
                minn = R[i][j];
                crr = make_pair(i, j);
            }
        }
    }
    
    fout << minn << " " << crr.first << " " << crr.second;
    
    
    
    
    return 0;
}