Cod sursa(job #2653591)

Utilizator ioana0211Ioana Popa ioana0211 Data 28 septembrie 2020 16:44:41
Problema Rj Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.24 kb
#include <fstream>
#include <iostream>
#include <queue>

using namespace std;
ofstream fout("rj.out");
const int NMAX=105;
int n, m;
int mat1[NMAX][NMAX], mat2[NMAX][NMAX];
int x1, y1, x2, y2, tmin=1000000, pozx, pozy;
int dx[]={0, -1, -1, -1, 0, 1, 1, 1};
int dy[]={-1, -1, 0, 1, 1, 1, 0, -1};
void read()
{
    ifstream fin ("rj.in");
    fin>>n>>m;
    fin.get();
    for(int i=1; i<=n; i++){
        char xx[NMAX];
        fin.getline(xx, NMAX);
        for(int j=1; j<=m; j++)
        {
            char x;
            x=xx[j-1];
            if(x=='X')
                mat1[i][j]=mat2[i][j]=-1;
            else if(x=='R')
            {
                mat1[i][j]=1;
                x1=i;
                y1=j;
            }
            else if(x=='J')
            {
                mat2[i][j]=1;
                x2=i;
                y2=j;
            }
        }
    }
}
void lee1()
{
    for(int i=0; i<=n+1; i++)
        mat1[i][0]=mat1[i][m+1]=-1;
    for(int j=0; j<=m+1; j++)
        mat1[0][j]=mat1[n+1][j]=-1;
    queue <pair<int, int>> q;
    q.push({x1, y1});
    while(!q.empty())
    {
        int x=q.front().first, y=q.front().second;
        for(int i=0; i<8; i++)
            if(mat1[x+dx[i]][y+dy[i]]==0)
        {
            mat1[x+dx[i]][y+dy[i]]=mat1[x][y]+1;
            q.push({x+dx[i], y+dy[i]});
        }
        q.pop();
    }
}
void lee2()
{
    for(int i=0; i<=n+1; i++)
        mat2[i][0]=mat2[i][m+1]=-1;
    for(int j=0; j<=m+1; j++)
        mat2[0][j]=mat2[n+1][j]=-1;
    queue <pair<int, int>> q;
    q.push({x2, y2});
    while(!q.empty())
    {
        int x=q.front().first, y=q.front().second;
        for(int i=0; i<8; i++)
            if(mat2[x+dx[i]][y+dy[i]]==0)
        {
            mat2[x+dx[i]][y+dy[i]]=mat2[x][y]+1;
            q.push({x+dx[i], y+dy[i]});
        }
        q.pop();
    }
}
void cmp ()
{
    for(int i=1; i<=n; i++)
        for(int j=1; j<=m; j++)
    {
        if(mat1[i][j]==mat2[i][j] && mat1[i][j]<tmin && mat1[i][j]>0)
        {
            tmin=mat1[i][j];
            pozx=i; pozy=j;
        }
    }
}
int main()
{
    read();
    lee1();
    lee2();
    cmp();
    fout<<tmin<<" "<<pozx<<" "<<pozy;
    return 0;
}