Cod sursa(job #3217459)

Utilizator deliaandreeaddelia andreea deliaandreead Data 23 martie 2024 09:57:49
Problema Rj Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.84 kb
#include <iostream>
#include <fstream>
#include <queue>

using namespace std;

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

struct point{
    int x;
    int y;
};
int dir_x[8]={0,-1,1,0,-1,1,-1,1};
int dir_y[8]={-1,0,0,1,-1,-1,1,1};
int distR[110][110];
int distJ[110][110];
int blocat[110][110];
queue<point>q;
string s;
int n,m;

bool in_mat(point poz){
    return poz.x>=1 && poz.x<=n && poz.y>=1 && poz.y<=m;
}

void lee(point start, int dist[110][110]){
    dist[start.x][start.y]=1;
    q.push(start);
    while(!q.empty()){
        point poz_in=q.front();
        q.pop();
        for(int i=0;i<8;i++){
            point poz_urm;
            poz_urm=poz_in;
            poz_urm.x+=dir_x[i];
            poz_urm.y+=dir_y[i];
            if(in_mat(poz_urm) && dist[poz_urm.x][poz_urm.y]==0 && blocat[poz_urm.x][poz_urm.y]==0){
                dist[poz_urm.x][poz_urm.y]=dist[poz_in.x][poz_in.y]+1;
                q.push(poz_urm);
            }
        }
    }
}

int main()
{
    fin>>n>>m;
    point R;
    point J;
    getline(fin,s);
    for(int i=1;i<=n;i++){
        getline(fin,s);
        //cout<<s<<endl;
        for(int j=0;j<m;j++){
            if(s[j]=='R'){
                R.x=i;
                R.y=j+1;
            }
            else if(s[j]=='J'){
                J.x=i;
                J.y=j+1;
            }
            else if(s[j]=='X'){
               blocat[i][j+1]=1;
            }
        }
    }
    lee(R,distR);
    lee(J,distJ);
    point rez;
    int t=100000;
    for(int i=0;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(distR[i][j]==distJ[i][j] && t>distR[i][j] && distR[i][j]>0){
                t=distR[i][j];
                rez.x=i;
                rez.y=j;
            }
        }
    }
    fout<<t<<" "<<rez.x<<" "<<rez.y;
    return 0;
}