Cod sursa(job #3208436)

Utilizator bogdibogdiAndrei Bogdan bogdibogdi Data 28 februarie 2024 17:15:46
Problema Rj Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.53 kb
#include <iostream>
#include <fstream>
#include <queue>
#include <climits>

using namespace std;

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

int n,m,istart,jstart,ifinal,jfinal,v[200][200],w[200][200],i,j;
int di[]={-1,-1,-1,0,0,1,1,1},dj[]={-1,0,1,-1,1,-1,0,1};

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

void lee()
{
    queue <pair<int,int>> q;
    q.push(make_pair(istart,jstart));
    v[istart][jstart]=1;
    while(!q.empty())
    {
        int icurent=q.front().first,jcurent=q.front().second;
        q.pop();
        for(int k=0;k<8;k++)
        {
            int iv=icurent+di[k],jv=jcurent+dj[k];
            if(inmatrice(iv,jv) && v[iv][jv]==0)
            {
                q.push(make_pair(iv,jv));
                v[iv][jv]=v[icurent][jcurent]+1;
            }
        }
        if(v[ifinal][jfinal]!=0) break;
    }

    /*for(i=1;i<=n;i++)
    {
        for(j=1;j<=m;j++)
        {
            cout<<v[i][j]<<" ";
        }
        cout<<endl;
    }*/

}

void lee2()
{
    queue <pair<int,int>> q;
    q.push(make_pair(ifinal,jfinal));
    w[ifinal][jfinal]=1;
    while(!q.empty())
    {
        int icurent=q.front().first,jcurent=q.front().second;
        q.pop();
        for(int k=0;k<8;k++)
        {
            int iv=icurent+di[k],jv=jcurent+dj[k];
            if(inmatrice(iv,jv) && w[iv][jv]==0)
            {
                q.push(make_pair(iv,jv));
                w[iv][jv]=w[icurent][jcurent]+1;
            }
        }
        if(w[istart][jstart]!=0) break;
    }

    /*cout<<endl;
    for(i=1;i<=n;i++)
    {
        for(j=1;j<=m;j++)
        {
            cout<<w[i][j]<<" ";
        }
        cout<<endl;
    }*/

}

int main()
{
    fin>>n>>m; fin.get();
    for(i=1;i<=n;i++)
    {
        char c[200];
        fin.getline(c,200);
        for(j=1;j<=m;j++)
        {
            if(c[j-1]==' ') v[i][j]=0;
            else if(c[j-1]=='X') v[i][j]=-1;
            else if(c[j-1]=='R') {istart=i; jstart=j; v[i][j]=0;}
            else { ifinal=i; jfinal=j; v[i][j]=0; }
            w[i][j]=v[i][j];
        }
    }
    lee();
    lee2();
    int mini=INT_MAX,savei,savej;
    for(i=1;i<=n;i++)
    {
        for(j=1;j<=m;j++)
        {
            if(v[i][j]!=-1 && v[i][j]!=0 && v[i][j]==w[i][j] && mini>v[i][j])
            {
                mini=v[i][j];
                savei=i;
                savej=j;
            }
        }
    }
    fout<<mini<<" "<<savei<<" "<<savej;
    return 0;
}