Cod sursa(job #2152261)

Utilizator alindima99Alin Dima alindima99 Data 5 martie 2018 13:17:41
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.52 kb
#include <fstream>
#include <queue>

using namespace std;

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

char mat[110][110];
int viz[110][110];
int lung[110][110], lung2[110][110];

pair<int, int> dim[8]={{-1, -1}, {-1, 0}, {-1, 1}, {0, -1}, {1, -1}, {1, 0}, {1, 1}, {0, 1}};

void reset(int n, int m)
{
    int i, j;

    for(i=0;i<=n+1;i++)
        for(j=0;j<=m+1;j++)
            viz[i][j]=0;
}

int main()
{
    int n, m, i, j, k, ij, jj;
    fin>>n>>m;
    fin.get();

    queue< pair<int, int> > coada;

    for(i=1;i<=n;i++)
        fin.getline(mat[i]+1, m+1);

    for(i=1;i<=n;i++)
        for(j=1;j<=m;j++)
            if(mat[i][j]=='R'){
                pair<int, int> pereche(i, j);
                coada.push(pereche);
                viz[coada.front().first][coada.front().second]=1;
            }

    while(!coada.empty()){
        pair<int, int> nod=coada.front();
        int i=nod.first, j=nod.second;
        lung[i][j]++;

        if(mat[i][j]=='J'){
            ij=i;
            jj=j;

            break;
        }

        for(k=0;k<=7;k++){
            int a=dim[k].first, b=dim[k].second;


            if(mat[i+a][j+b]!=0 && mat[i+a][j+b]!='X' && viz[i+a][j+b]==0){
                pair <int, int> x(i+a, j+b);
                viz[i+a][j+b]=1;
                lung[i+a][j+b]+=lung[i][j];
                coada.push(x);
            }
        }

        coada.pop();
    }

    //JULIETA
    queue< pair<int, int> > temp;
    swap(coada, temp);
    pair<int, int> pereche(ij, jj);
    coada.push(pereche);
    reset(n, m);
    viz[coada.front().first][coada.front().second]=1;

    while(!coada.empty()){
        pair<int, int> nod=coada.front();
        int i=nod.first, j=nod.second;
        lung2[i][j]++;

        if(mat[i][j]=='R')
            break;

        for(k=0;k<=7;k++){
            int a=dim[k].first, b=dim[k].second;


            if(mat[i+a][j+b]!=0 && mat[i+a][j+b]!='X' && viz[i+a][j+b]==0){
                pair <int, int> x(i+a, j+b);
                viz[i+a][j+b]=1;
                lung2[i+a][j+b]+=lung2[i][j];
                coada.push(x);
            }
        }

        coada.pop();
    }

    int mini=999, minj=999, l=999;
    for(i=1;i<=n;i++)
        for(j=1;j<=m;j++)
            if((lung[i][j]==lung2[i][j]) && (lung[i][j]!=0) && lung[i][j]<l){
                l=lung[i][j];
                mini=i;
                minj=j;
            }

    cout<<lung[mini][minj]<<" "<<mini<<" "<<minj;

    return 0;
}