Cod sursa(job #2664335)

Utilizator DenisaCantuCantu Denisa DenisaCantu Data 28 octombrie 2020 15:24:47
Problema Rj Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.93 kb
#include <iostream>
#include <fstream>
#include <queue>

using namespace std;

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

int n, m, r[101][101], j[101][101], xr, yr, xj, yj, tmin = 100000;
queue < int > qx, qy;
int dx[8]= {-1,-1,-1,0,0,1,1,1};
int dy[8]= {-1,0,1,-1,1,-1,0,1};

bool verifica(int x,int y)
{
    if(x > 0 && x <= n && y > 0 && y <= m)
        return 1;
    else
        return 0;
}

void BFS ( int m[101][101], int x, int y)
{
    qx.push(x);
    qy.push(y);
    while(!qx.empty())
    {
        int cx = qx.front();
        int cy = qy.front();
        for (int i = 0; i < 8; i++)
        {
            int nx = cx + dx[i];
            int ny = cy + dy[i];
            if (verifica ( nx, ny) == 1 && !m[nx][ny])
            {
                m[nx][ny] = m[cx][cy] + 1;
                qx.push(nx);
                qy.push(ny);
            }
        }
        qx.pop();
        qy.pop();
    }
}
int main()
{
    in>>n>>m;
    in.get();
    for(int i = 1; i <= n; i++)
    {
        char s[150];
        in.getline(s,105);
        for(int k = 0; k < m; k++)
        {
            if( s[k] == 'R')
            {
                xr = i;
                yr = k + 1;
                r[i][k + 1] = 1;
            }
            else if(s[k] == 'J')
            {
                xj = i;
                yj = k + 1;
                j[i][k+1] = 1;
            }
            else if(s[k] == 'X')
            {
                r[i][k+1] = j[i][k+1] = -1;
            }
        }
    }
    BFS (r, xr, yr);
    BFS (j, xj, yj);
    int fx, fy;
    for(int i = 1; i <= n; i++)
    {
        for(int k = 1; k <= m; k++)
        {
            if(r[i][k] == j[i][k] && r[i][k] < tmin && j[i][k] > 0)
            {
                tmin = r[i][k];
                fx = i;
                fy = k;
            }
        }
    }
    out << tmin << " " << fx << " " << fy;
    return 0;
}