Cod sursa(job #2699513)

Utilizator radu3400Negulescu Radu-Andrei radu3400 Data 24 ianuarie 2021 19:21:47
Problema Rj Scor 50
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3 kb
#include <iostream>
#include <string.h>
#include <fstream>
#include <vector>
#include <queue>
#include <tuple>
using namespace std;
ifstream f("rj.in");
ofstream g("rj.out");
int n,m;
vector<vector<int>> mat;
vector<vector<int>> matR;
vector<vector<int>> matJ;
vector<vector<int>> viz;
vector<vector<tuple<int,int>>> tataR;
vector<vector<tuple<int,int>>> tataJ;
queue<tuple<int,int>> coada;
int d1[8]={-1,-1,-1,0,1,1,1,0};
int d2[8]={-1,0,1,1,1,0,-1,-1};
void bf(int a, int b, vector<vector<int>> mat, vector<vector<int>> &mat2, int n, int m, vector<vector<tuple<int,int>>> &tata, vector<vector<int>> viz){
    coada.push(make_tuple(a,b));
    viz[a][b] = 1;
    while(!coada.empty()){
        tuple<int,int> t = coada.front();
        int x = get<0>(t);
        int y = get<1>(t);
        coada.pop();
        for(int i=0;i<8;i++){
            int x2 = x+d1[i];
            int y2 = y+d2[i];
            if(x2>=0&&x2<n&&y2>=0&&y2<m&&mat[x2][y2]!=1&&viz[x2][y2]==0){
                viz[x2][y2] = 1;
                mat2[x2][y2] = mat2[x][y]+1;
                tata[x2][y2] = make_tuple(x,y);
                coada.push(make_tuple(x2,y2));
            }
        }
    }
}
int main()
{
    f>>n>>m;
    for(int i=0;i<n;i++){
        vector<int> aux;
        vector<tuple<int,int>> aux2;
        mat.push_back(aux);
        matR.push_back(aux);
        matJ.push_back(aux);
        viz.push_back(aux);
        tataJ.push_back(aux2);
        tataR.push_back(aux2);
        for(int j=0;j<m;j++){
            mat[i].push_back(0);
            matR[i].push_back(-1);
            matJ[i].push_back(-1);
            viz[i].push_back(0);
            tataR[i].push_back(make_tuple(-1,-1));
            tataJ[i].push_back(make_tuple(-1,-1));
        }
    }
    int xr,yr,xj,yj;
    f.get();
    for(int i=0;i<n;i++){
        char s[100]="";
        f.getline(s,100,'\n');
        for(int j=0;j<m;j++){
            switch(s[j]){
                case 'R':
                    mat[i][j] = -1;
                    xr = i;
                    yr = j;
                    break;
                case 'J':
                    mat[i][j] = -2;
                    xj = i;
                    yj = j;
                    break;
                case 'X':
                    mat[i][j] = 1;
                    break;
                default:
                    mat[i][j] = 0;
                    break;
            }
        }
    }
    matR[xr][yr] = 1;
    matJ[xj][yj] = 1;
    bf(xr,yr,mat,matR,n,m,tataR,viz);
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            viz[i][j] = 0;
        }
    }
    bf(xj,yj,mat,matJ,n,m,tataJ,viz);
    int l,c;
    int mini = n*m;
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            if(matR[i][j] == matJ[i][j] && matR[i][j]+matJ[i][j]<mini && matJ[i][j]>=0){
                mini = matR[i][j]+matJ[i][j];
                l = i;
                c = j;
            }
        }
    }
    g<<mini/2<<" "<<l+1<<" "<<c+1;
}