Cod sursa(job #2507386)

Utilizator FasoleboiTudor Gadalean Fasoleboi Data 10 decembrie 2019 09:48:10
Problema Rj Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.3 kb
#include <bits/stdc++.h>
using namespace std;

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

queue < pair < int, int > > q;
int n, m, sr[101][101], sj[101][101];
int x, y, timp=101, ri, rj, ji, jj;
char s[101];

int di[8]={0, 0, -1, 1, -1, 1, -1, 1};
int dj[8]={-1, 1, 0, 0, -1, -1, 1, 1};

void leej(int i, int j){
    q.push(make_pair(i, j));
    while(!q.empty()){
        int i=q.front().first;
        int j=q.front().second;
        q.pop();
        for(int k=0;k<8;k++){
            int ni=i+di[k];
            int nj=j+dj[k];
            if(sj[ni][nj]!=-1 && sj[ni][nj]==0){
                sj[ni][nj]=sj[i][j]+1;
                q.push(make_pair(ni, nj));
            }
        }
    }
}

void leer(int i, int j){
    q.push(make_pair(i, j));
    while(!q.empty()){
        int i=q.front().first;
        int j=q.front().second;
        q.pop();
        for(int k=0;k<8;k++){
            int ni=i+di[k];
            int nj=j+dj[k];
            if(sr[ni][nj]!=-1 && sr[ni][nj]==0){
                sr[ni][nj]=sr[i][j]+1;
                q.push(make_pair(ni, nj));
            }
        }
    }
}

void bordare(){
    for(int i = 0; i <= n + 1; i++) {
        sr[i][0] = -1;
        sj[i][0] = -1;
        sr[i][m+1] = -1;
        sj[i][m+1] = -1;
    }
    for(int j = 0; j <= m + 1; j++) {
        sr[0][j] = -1;
        sj[0][j] = -1;
        sr[n+1][j] = -1;
        sj[n+1][j] = -1;
    }
}

int main(){
    fin>>n>>m;
    fin.getline(s, 101);
    for(int i=1;i<=n;i++){
        fin.getline(s, 101);
        for(int j=1;j<=m;j++){
            if(s[j-1]=='R'){
                sr[i][j]=1;
                ri=i;
                rj=j;
            }else if(s[j-1]=='J'){
                sj[i][j]=1;
                ji=i;
                jj=j;
            }else if(s[j-1]=='X'){
                sr[i][j] = sj[i][j] = -1;
            }else{
                sr[i][j]=sj[i][j]=0;
            }
        }
    }
    bordare();
    leer(ri,rj);
    leej(ji,jj);
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(sr[i][j]==sj[i][j] && sj[i][j]>0 && sj[i][j]<timp){
                    timp = sj[i][j];
                    x = i;
                    y = j;
            }
        }
    }
    fout<<timp<<" "<<x<<" "<<y;
    return 0;
}