Cod sursa(job #2653627)

Utilizator vlad414141414141Vlad Ionescu vlad414141414141 Data 28 septembrie 2020 17:32:28
Problema Rj Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.68 kb
#include <iostream>
#include <fstream>
#include <queue>
#include <cstring>

using namespace std;

const int MAX=1041;

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

int n, m, x1, y1, x2, y2;
int matr[MAX][MAX], matj[MAX][MAX];
int dx[]={0,-1,-1,-1,0,1,1,1}, dy[]={-1,-1,0,1,1,1,0,-1};
char v[1041];

void read()
{
    fin >> n >> m;
    fin.get();
    for (int i=1;i<=n;++i)
    {
        fin.getline(v+1,141);
        for (int j=1;j<=m;++j)
        {
            if (v[j]=='R'){
                x1=i;y1=j;
            }
            else if (v[j]=='J'){
                x2=i;y2=j;
            }
            else if (v[j]=='X'){
                matr[i][j]=-1;
                matj[i][j]=-1;
            }
           // cout << matr[i][j] << " ";
        }
       // cout << "\n";
    }
}

void lee()
{
    for (int i=0;i<=n+1;++i)
    {
        matr[i][0]=-1;
        matr[i][m+1]=-1;
    }
    for (int i=0;i<=m+1;++i)
    {
        matr[0][i]=-1;
        matr[n+1][i]=-1;
    }
    matr[x1][y1]=1;
    queue<pair<int,int>> coada;
    coada.push({x1,y1});
    while (!coada.empty())
    {
        int indi, indj;
        indi=coada.front().first;
        indj=coada.front().second;
        coada.pop();
        for (int d=0;d<8;++d)
        {
            if (matr[indi+dx[d]][indj+dy[d]]==0)
            {
                coada.push({indi+dx[d],indj+dy[d]});
                matr[indi+dx[d]][indj+dy[d]]=matr[indi][indj]+1;
            }
        }
    }
}

void lee2()
{
    for (int i=0;i<=n+1;++i)
    {
        matr[i][0]=-1;
        matr[i][m+1]=-1;
    }
    for (int i=0;i<=m+1;++i)
    {
        matr[0][i]=-1;
        matr[n+1][i]=-1;
    }
    matj[x2][y2]=1;
    queue<pair<int,int>> coada;
    coada.push({x2,y2});
    while (!coada.empty())
    {
        int indi, indj;
        indi=coada.front().first;
        indj=coada.front().second;
        coada.pop();
        for (int d=0;d<8;++d)
        {
            if (matj[indi+dx[d]][indj+dy[d]]==0)
            {
                coada.push({indi+dx[d],indj+dy[d]});
                matj[indi+dx[d]][indj+dy[d]]=matj[indi][indj]+1;
            }
        }
    }
}

int main()
{
    read();
    lee();
    lee2();
    int minim=10041, auxi, auxj;
    for (int i=1;i<=n;++i)
    {
        for (int j=1;j<=m;++j)
        {
          //  cout << matr[i][j] << " ";
            if (matr[i][j]==matj[i][j]&&matr[i][j]>0&&matr[i][j]<minim)
            {
                auxi=i;
                auxj=j;
                minim=matr[i][j];
            }
        }
        //cout << endl;
    }

    fout << minim << " " << auxi << " " << auxj;
    return 0;
}