Cod sursa(job #2176124)

Utilizator SpiriFlaviuBerbecariu Flaviu SpiriFlaviu Data 16 martie 2018 21:01:37
Problema Rj Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.26 kb
#include <iostream>
#include <fstream>
#include <cstring>
#include <queue>
using namespace std;

ifstream f("rj.in");
ofstream g("rj.out");
int n,m;

int a[101][101];
int color[101][101];

int rx, ry, jx, jy;

int di[8]={-1,-1,-1,0,0,1,1,1};
int dj[8]={-1,0,1,-1,1,-1,0,1};

bool inside(int i,int j)
{
    return i>0 && j>0 && i<=n && j<=m;
}

int solx = 10000, soly=10000, t = 0;

void latime()
{
    queue<pair<int,int > > Q;
    Q.push(make_pair(rx,ry));
    Q.push(make_pair(jx,jy));
    color[rx][ry]=1;
    color[jx][jy]=2;
    a[rx][ry]=1;
    a[jx][jy]=1;

    while(!Q.empty())
    {
        int i=Q.front().first;
        int j=Q.front().second;
        for(int k=0;k<8;k++)
        {
            int inou=i+di[k];
            int jnou=j+dj[k];
            if(inside(inou,jnou))
            {
                if(a[inou][jnou] ==0)
                {
                    a[inou][jnou]=a[i][j]+1;
                    color[inou][jnou] = color[i][j];
                    Q.push(make_pair(inou,jnou));
                }
                else if(a[inou][jnou] > 0 && color[inou][jnou] != color[i][j])
                {
                    if(!t ||
                       ( t && inou < solx)||
                       ( t && inou == solx && jnou < soly))
                    {
                         solx=inou;
                        soly=jnou;
                        t = a[inou][jnou];
                    }

                }
            }
        }
        Q.pop();
    }
}
void afis_mat()
{

    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= m; j++)
        {
            cout<<a[i][j]<<' ';
        }
        cout<<'\n';
    }
}
int main()
{
    f>>n>>m;
    char c[101];
    f.getline(c,100);
    for(int i = 1; i<=n ;i ++)
    {
        f.getline(c,100);
        for(int j = 1 ; j <= m; j++)
            if(c[j-1] == 'X')
                a[i][j] = -1;
            else if(c[j-1]=='R')
            {
                rx = i;
                ry = j;
            }
            else if(c[j-1]=='J')
            {
                jx = i;
                jy = j;
            }

    }
   // afis_mat();
    latime();
    g<<t<<' '<<solx<<' '<<soly<<'\n';
    //afis_mat();
    return 0;
}