Cod sursa(job #3205960)

Utilizator vladdobro07vladdd vladdobro07 Data 21 februarie 2024 10:58:19
Problema Rj Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.07 kb
#include <bits/stdc++.h>
using namespace std;
ifstream fin("rj.in");
ofstream fout("rj.out");
const int nmax=100,inf=79797979;
const int dx[]= {0,1,0,-1,-1,-1,1,1};
const int dy[]= {1,0,-1,0,-1,1,-1,1};
int mn[2][nmax+1][nmax+1];
char v[nmax+1][nmax+1];
string s;
int n,m,xj,yj,xr,yr;
void read() {
        fin>>n>>m;
        char c;
        int i=1,j=0;
        while((c=fin.get())) {
                if(c==' '||c=='R'||c=='X'||c=='J') {
                        if(j==m) {
                                i++;
                                j=1;
                        } else
                                j++;
                        v[i][j]=c;
                        if(v[i][j]=='R') {
                                xr=i;
                                yr=j;
                        }
                        if(v[i][j]=='J') {
                                xj=i;
                                yj=j;
                        }
                }
                if(c==EOF)
                        return;
        }
}
void infi(int a[nmax+1][nmax+1]) {
        for(int i=1; i<=n; i++) {
                for(int j=1; j<=m; j++) {
                        a[i][j]=inf;
                }
        }
}
bool in(int x,int y) {
        return (1<=x&&x<=n&&1<=y&&y<=m);
}
void bfs(int xs,int ys,int a[nmax+1][nmax+1]) {
        queue<pair<int,int>> q;
        infi(a);
        q.push({xs,ys});
        a[xs][ys]=1;
        while(!(q.empty())) {
                int xc=q.front().first,yc=q.front().second;
                //fout<<xc<<" "<<yc<<" "<<a[xc][yc]<<"\n";
                q.pop();
                for(int i=0; i<8; i++) {
                        int nx=xc+dx[i],ny=yc+dy[i];
                        if(in(nx,ny)) {
                                if(v[nx][ny]==' ') {
                                        if(a[nx][ny]>a[xc][yc]+1) {
                                                a[nx][ny]=a[xc][yc]+1;
                                                q.push({nx,ny});
                                        }
                                }
                        }
                }
        }
        //fout<<"\n";
}
void print(auto a[nmax+1][nmax+1]) {
        for(int i=1; i<=n; i++) {
                for(int j=1; j<=m; j++)
                        fout<<a[i][j]<<" ";
                fout<<"\n";
        }
        fout<<"\n";
}
pair<int,int> solve() {
        int minn=inf;
        pair<int,int> rez;
        for(int i=1; i<=n; i++) {
                for(int j=1; j<=m; j++) {
                        if(mn[0][i][j]==mn[1][i][j]) {
                                if(mn[0][i][j]<minn) {
                                        minn=mn[0][i][j];
                                        rez= {i,j};
                                }
                        }
                }
        }
        return rez;
}
int main() {
        read();
        bfs(xj,yj,mn[0]);
        bfs(xr,yr,mn[1]);
        //print(v);
        fout<<solve().first<<" "<<solve().second<<" "<<mn[0][solve().first][solve().second];
        return 0;
}