Cod sursa(job #2334604)

Utilizator DanielznaceniDaniel Danielznaceni Data 2 februarie 2019 18:50:55
Problema Rj Scor 50
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.96 kb
#include <iostream>
#include <fstream>
#include <cstring>
#include <queue>
#define lmax 101

using namespace std;

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

bool nou[lmax][lmax];
int n, m, mat[lmax][lmax], romeo[lmax][lmax], lmin=(lmax*lmax), a, b, w, d, f, g;
char s[lmax];
int di[]={-1, -1, -1, 0, 0, 1, 1, 1};
int dj[]={-1, 0, 1, -1, 1, -1, 0, 1};
queue <pair<int, int> > q;

int Is_in_matrix(int i, int j)
{
    if(i>0 && i<=n && j>0 && j<=m)
        return 1;
    return 0;
}

void leej(int x, int y)
{
    q.push(make_pair(x, y));
    nou[x][y]=1;
    while(!q.empty())
    {
        int i, ii, j, jj;
        i=q.front().first;
        j=q.front().second;
        for(int ij=0; ij<=7; ++ij)
        {
            ii=i+di[ij];
            jj=j+dj[ij];
            if(Is_in_matrix(ii, jj) && nou[ii][jj]==0 && mat[ii][jj]>=0)
            {
                mat[ii][jj]=mat[i][j]+1;
                nou[ii][jj]=1;
                q.push(make_pair(ii, jj));
            }
        }
        q.pop();
    }
}

void leer(int x, int y)
{
    q.push(make_pair(x, y));
    nou[x][y]=1;
    while(!q.empty())
    {
        int i, ii, j, jj;
        i=q.front().first;
        j=q.front().second;
        for(int ij=0; ij<=7; ++ij)
        {
            ii=i+di[ij];
            jj=j+dj[ij];
            if(Is_in_matrix(ii, jj) && nou[ii][jj]==0 && romeo[ii][jj]>=0)
            {
                romeo[ii][jj]=romeo[i][j]+1;
                /*if(mat[ii][jj]==romeo[ii][jj] && mat[ii][jj]<lmin)
                {
                    lmin=mat[ii][jj];
                    a=ii;
                    b=jj;
                }*/
                nou[ii][jj]=1;
                q.push(make_pair(ii, jj));
            }
        }
        q.pop();
    }
}

int main()
{
    in>>n>>m;
    for(int i=0; i<=n; ++i)
    {
        in.getline(s, 100);
        for(int j=0; j<m && i>=1; ++j)
        {

            if(s[j]==' ')
            {
                mat[i][j+1]=0;
            }
            else if(s[j]=='X')
            {
                mat[i][j+1]=-1;
                romeo[i][j+1]=-1;
            }
            if(s[j]=='R')
            {
                romeo[i][j+1]=1;
                mat[i][j+1]=1;
                w=i;
                d=j+1;
            }
            if(s[j]=='J')
            {
                mat[i][j+1]=1;
                romeo[i][j+1]=1;
                f=i;
                g=j+1;
            }
        }
    }
    leej(f, g);
    for(int i=1; i<=n; ++i)
    {
        for(int j=1; j<=m; ++j)
        {
            nou[i][j]=0;
        }
    }
    leer(w, d);
    for(int i=1; i<=n; ++i)
    {
        for(int j=1; j<=m; ++j)
        {
            if(mat[i][j]==romeo[i][j] && mat[i][j]>0 && mat[i][j]<lmin)
            {
                lmin=mat[i][j];
                a=i;
                b=j;
            }
        }
    }
    out<<lmin<<" "<<a<<" "<<b;
    return 0;
}