Cod sursa(job #2668545)

Utilizator TaveNeagoe Gabriel-Octavian Tave Data 5 noiembrie 2020 00:10:47
Problema Rj Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.43 kb
#include <fstream>
#include <bits/stdc++.h>

using namespace std;
 
ifstream f("rj.in");
ofstream g("rj.out");
 
struct cell{
    int x, y;
};

queue<cell> q1, q2;
int N, M;
int mat1[1010][1010], mat2[1010][1010];

void bfs12 (cell start1, cell start2){
    int x, y;
    cell poz, aux;
    mat1[start1.x][start1.y] = mat2[start2.x][start2.y] = 1;
    q1.push(start1);
    q2.push(start2);

    
    while(!q1.empty()){
        poz = q1.front();
        q1.pop();
        
        //g<<"Consider elementul x="<<poz.x<<" y="<<poz.y<<" elem="<<mat1[poz.x][poz.y]<<endl;

        for(x=-1; x<=1; x++)
            for(y=-1; y<=1; y++){

                aux.x = poz.x + x;
                aux.y = poz.y + y;

                //g<<(aux.x<N)<<" "<<(aux.x>=0)<<" "<<(aux.y<M)<<" "<<(aux.y>=0)<<" "<<(x!=0 || y!=0)<<" "<<(mat1[aux.x][aux.y]==0)<<"\n\n\n";

                if((aux.x<=N && aux.x>=1) && (aux.y<=M && aux.y>=1) && (x!=0 || y!=0)){
                    if(mat1[aux.x][aux.y]==0 && mat1[aux.x][aux.y]!=-1){
                        mat1[aux.x][aux.y] = mat1[poz.x][poz.y] + 1;
                        q1.push(aux);
                        //g<<mat1[aux.x][aux.y]<<" "<<aux.x<<" "<<aux.y<<"\n";
                    }
                }
            }
    }

    while(!q2.empty()){
        poz = q2.front();
        q2.pop();
        
        //g<<"Consider elementul x="<<poz.x<<" y="<<poz.y<<" elem="<<mat2[poz.x][poz.y]<<endl;

        for(x=-1; x<=1; x++)
            for(y=-1; y<=1; y++){

                aux.x = poz.x + x;
                aux.y = poz.y + y;

                //g<<(aux.x<N)<<" "<<(aux.x>=0)<<" "<<(aux.y<M)<<" "<<(aux.y>=0)<<" "<<(x!=0 || y!=0)<<" "<<(mat1[aux.x][aux.y]==0)<<"\n\n\n";

                if((aux.x<=N && aux.x>=1) && (aux.y<=M && aux.y>=1) && (x!=0 || y!=0)){
                    if(mat2[aux.x][aux.y]==0 && mat2[aux.x][aux.y]!=-1){
                        mat2[aux.x][aux.y] = mat2[poz.x][poz.y] + 1;
                        q2.push(aux);
                        //g<<mat2[aux.x][aux.y]<<" "<<mat2[poz.x][poz.y]<<"\n";
                    }
                }
            }
    }
}

int main(){
    f>>N>>M;
    char line[105];
    int i, j, trez=105;
    cell rom, jul, rez;
    f.get();
    for(i=0; i<N; i++){
        f.getline(line, M+5);
        for(j=0; j<M; j++){
            if(line[j]=='R'){
                mat1[i+1][j+1] = mat2[i+1][j+1] = 0;
                rom.x = i+1;
                rom.y = j+1;
            }
            else if(line[j]=='J'){
                mat1[i+1][j+1] = mat2[i+1][j+1] = 0;
                jul.x = i+1;
                jul.y = j+1;
            }
            else if(line[j]=='X')
                mat1[i+1][j+1] = mat2[i+1][j+1] = -1;

            else if(line[j]==' ')
                mat1[i+1][j+1] = mat2[i+1][j+1] = 0;    
        }
    }

    bfs12(rom, jul);

    /*for (i=1; i<=N; i++){
        g<<endl;
        for(j=1; j<=M; j++){
            g<<mat1[i][j]<<" ";
        }
    }
    g<<"\n\n\n";
    for (i=1; i<=N; i++){
        g<<endl;
        for(j=1; j<=M; j++){
            g<<mat2[i][j]<<" ";
        }
    }*/

    for (i=0; i<N; i++)
        for(j=0; j<M; j++)
            if(mat1[i][j]<trez && mat2[i][j]==mat1[i][j] && mat1[i][j]>0){
                trez = mat1[i][j];
                rez.x = i;
                rez.y = j;
            }

    g<<trez<<" "<<rez.x<<" "<<rez.y;

    return 0;
}