Cod sursa(job #2784948)

Utilizator RobertAcAcatrinei Robert-Marian RobertAc Data 17 octombrie 2021 18:55:31
Problema Rj Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.65 kb
#include <bits/stdc++.h>
#define nmax 101
#define x first
#define y second
using namespace std;
string prob="rj";
ifstream in(prob+".in");
ofstream out(prob+".out");
int dist[nmax][nmax][2];
queue<pair<int,int> > q;
int n,m;
void lee(int a){
    while(!q.empty()){
        int x=q.front().x;
        int y=q.front().y;
        q.pop();
        if(x-1>0){
            if(!dist[x-1][y][a]){
                dist[x-1][y][a]=dist[x][y][a]+1;
                q.push({x-1,y});
            }
        }
        if(x+1<=n){
            if(!dist[x+1][y][a]){
                dist[x+1][y][a]=dist[x][y][a]+1;
                q.push({x+1,y});
            }
        }
        if(y-1>0){
            if(!dist[x][y-1][a]){
                dist[x][y-1][a]=dist[x][y][a]+1;
                q.push({x,y-1});
            }
        }
        if(y+1<=m){
            if(!dist[x][y+1][a]){
                dist[x][y+1][a]=dist[x][y][a]+1;
                q.push({x,y+1});
            }
        }
        if(x-1>0&&y-1>0){
            if(!dist[x-1][y-1][a]){
                dist[x-1][y-1][a]=dist[x][y][a]+1;
                q.push({x-1,y-1});
            }
        }
        if(x+1<=n&&y+1<=m){
            if(!dist[x+1][y+1][a]){
                dist[x+1][y+1][a]=dist[x][y][a]+1;
                q.push({x+1,y+1});
            }
        }
        if(y-1>0&&x+1<=n){
            if(!dist[x+1][y-1][a]){
                dist[x+1][y-1][a]=dist[x][y][a]+1;
                q.push({x+1,y-1});
            }
        }
        if(y+1<=m&&x-1>0){
            if(!dist[x-1][y+1][a]){
                dist[x-1][y+1][a]=dist[x][y][a]+1;
                q.push({x-1,y+1});
            }
        }
    }
}
int main(){
    in>>n>>m;
    string s;
    int xr,yr,xj,yj;
    getline(in,s);
    for(int i=0;i<n;i++){
        getline(in,s);
        for(int j=0;j<s.size();j++){
            if(s[j]=='R'){
                xr=i+1;
                yr=j+1;
            }else if(s[j]=='J'){
                xj=i+1;
                yj=j+1;
            }else if(s[j]=='X'){
                dist[i+1][j+1][0]=dist[i+1][j+1][1]=INT_MAX;
            }
        }
    }
    dist[xr][yr][0]=1;
    q.push({xr,yr});
    lee(0);
    dist[xj][yj][1]=1;
    q.push({xj,yj});
    lee(1);
    int minn=INT_MAX;
    int xm,ym;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(dist[i][j][0]==dist[i][j][1]&&dist[i][j][1]){
                if(dist[i][j][0]<minn){
                    minn=dist[i][j][0];
                    xm=i;
                    ym=j;
                }
            }
        }
    }
    out<<minn<<' '<<xm<<' '<<ym;
}