Cod sursa(job #2667505)

Utilizator hirneagabrielHirnea Gabriel hirneagabriel Data 3 noiembrie 2020 15:40:13
Problema Rj Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.37 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>

using namespace std;

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


int Graf[1001][1001][2],sol;
queue<pair <int,int>> coada;
int X[9] = { -1, -1, -1, 0, 1, 1, 1, 0 };
int Y[9] = { -1, 0, 1, 1, 1, 0, -1, -1 };
int n,m;

void bfs(int x,int y,int index_mat)
{
   
    coada.push(make_pair(x,y));
    while (!coada.empty())
    {
        int a, b,aa,bb;
        a = coada.front().first;
        b = coada.front().second;
        coada.pop();
        for (int i = 0; i < 8; i++)
        {
            aa = a + X[i];
            bb = b + Y[i];
            if (aa > 0 && aa <= n && bb > 0 && bb <= m && Graf[aa][bb][index_mat] == 0)
            {
                Graf[aa][bb][index_mat] = Graf[a][b][index_mat]+1;
                coada.push(make_pair(aa, bb));
            }
        }
    }
}

int main() {
    int xr, yr,xj,yj,sol=1000000,x,y;
    fin >> n >> m;

    fin.get();
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            char c;
            c = fin.get();
            if (c == 'R')
            {
                Graf[i][j][0] = 1;
                xr = i;
                yr = j;
            }
            else if (c == 'J')
            {
                Graf[i][j][1] = 1;
                xj = i;
                yj = j;
            }
            else if (c == 'X')
            {
                Graf[i][j][0] = -1;
                Graf[i][j][1] = -1;
            }
            else {
                Graf[i][j][0] = 0;
                Graf[i][j][0] = 0;
            }
            
        }
        fin.get();
    }
    /*for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
            cout << Graf[i][j][0] << " ";
        cout << endl;
    }*/
   bfs(xr, yr, 0);
   bfs(xj, yj, 1);
   /*for (int i = 1; i <= n; i++)
   {
       for (int j = 1; j <= m; j++)
           cout << Graf[i][j][0] << " ";
       cout << endl;
   }*/
    for(int i=1;i<=n;i++)
        for (int j = 1; j <= m; j++)
        {
            if (Graf[i][j][0] > 0 && Graf[i][j][0] == Graf[i][j][1] && Graf[i][j][0] < sol)
            {
                sol = Graf[i][j][0];
                x = i;
                y = j;
            }
        }

    fout << sol << " " << x << " " << y;
    return 0;
}