Cod sursa(job #2425414)

Utilizator CameliaSSamoilescu Camelia CameliaS Data 24 mai 2019 19:56:43
Problema Rj Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.4 kb
#include <iostream>
#include <fstream>
#include <queue>

using namespace std;
ifstream f("rj.in");
ofstream g("rj.out");
#define NMAX 105
const int dx[] = {0,0,1,1,1,-1,-1,-1};
const int dy[] = {-1,1,0,-1,1,0,-1,1};


int MR[NMAX][NMAX], MJ[NMAX][NMAX], n, m;
queue<pair<int, int> > q;
pair<int, int> startR,startJ;

void citire()
{
    char x;
    f>>n>>m;
    f.get();
    for(int i = 1; i <= n; i ++)
    {
        for(int j = 1; j <= m; j ++)
        {

            f.get(x);

            if(x == 'R')
            {
                MR[i][j] = 1;
                MJ[i][j] = 0;
                startR = {i,j};
            }
            else if(x == 'J')
            {
                MR[i][j] =0;
                MJ[i][j]= 1;
                startJ = {i,j};
            }
            else if(x == 'X')
            {
                MR[i][j] =-1;
                MJ[i][j]= -1;

            }

            else
            {
                MR[i][j] = 0;
                MJ[i][j]= 0;
            }

        }
        f.get();
    }

    for(int i = 0; i <= m+1; i ++)
        MR[0][i] = MR[n+1][i] =  MJ[0][i] = MJ[n+1][i] = -2;
    for(int i = 0; i <= n+1; i ++)
        MR[i][0] = MR[i][m+1] =  MJ[i][0] = MJ[i][m+1] = -2;


}

void bfs(int m[NMAX][NMAX], pair<int, int> start)
{

    q.push(start);
    while(!q.empty())
    {
        pair<int, int> fg = q.front();
        q.pop();
        int x = fg.first;
        int y = fg.second;
        for(int i = 0; i < 8; i ++)
        {

            int xx = x + dx[i];
            int yy = y + dy[i];
            if((m[xx][yy] > 0 && m[x][y] + 1< m[xx][yy]) || m[xx][yy] == 0)
            {
                m[xx][yy]=  1 + m[x][y];
                q.push({xx,yy});
            }

        }
    }

}
void afisare()
{
    for(int i = 1; i <= n; i ++)
    {
        for(int j = 1; j <= m; j ++)
            cout<<MR[i][j]<<" ";
        cout<<'\n';

    }
}
int main()
{
    citire();
    queue<int>r,j;
    //afisare();
    bfs(MR,startR);
    bfs(MJ,startJ);

    int miin = n*m+1, ri, rj;
    for(int i = 1; i <= n; i ++)
        for(int j = 1; j <= m; j++)
            if(MR[i][j] > 0 && MR[i][j] == MJ[i][j] && MR[i][j] < miin)
            {
                ri = i;
                rj = j;
                miin = MR[i][j];
            }
    g<<miin<<" "<<ri<<" "<<rj;
    return 0;
}