Cod sursa(job #3205261)

Utilizator Bogdan345Marius Mihalache Bogdan345 Data 19 februarie 2024 09:51:27
Problema Rj Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.82 kb
#include <fstream>
#include <queue>
#include <vector>
using namespace std;
ifstream cin("rj.in");
ofstream cout("rj.out");
queue<pair<int,int>>q;
vector<vector<char>>mat;
vector<vector<int>>distanta;
vector<int>x={1,-1,0,0,1,1,-1,-1},y={0,0,1,-1,-1,1,-1,1};
const int inf=1e9;
void bfs(int n,int m,int& rasp,int& a,int& b){
    while(!q.empty()){
        pair<int,int>poz=q.front();
        q.pop();
        int i,j;
        for(int u=0;u<=3;u++){
            i=poz.first+x[u];
            j=poz.second+y[u];
            if(i>n || i<1 || j>m || j<1 || mat[i][j]=='X'){
                continue;
            }
            if(distanta[i][j]>distanta[poz.first][poz.second]+1){
                distanta[i][j]=distanta[poz.first][poz.second]+1;
                q.push({i,j});

            }else if(distanta[i][j]==distanta[poz.first][poz.second]+1){
                if(rasp>distanta[i][j]){
                    rasp=distanta[i][j];
                    a=i;
                    b=j;
                }else if(rasp==distanta[i][j]){
                    if(a>i || (a>=i && b>=j)){
                        a=i;
                        b=j;
                    }
                }
            q.push({i,j});
            }
        }
    }
}
int main(){
    int n,m;
    cin>>n>>m;
    mat.resize(n+1,vector<char>(m+1));
    distanta.resize(n+1,vector<int>(m+1,inf));
    string s;
    for(int i=0;i<=n;i++){
        getline(cin,s);
        for(int j=0;j<s.size();j++){
            mat[i][j+1]=s[j];
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(mat[i][j]=='R' or mat[i][j]=='J'){
                distanta[i][j]=0;
                q.push({i,j});
            }
        }
    }
    int a=-1,b=-1,rasp=1e9;
    bfs(n,m,rasp,a,b);
    cout<<rasp<<" "<<a<<" "<<b;
}