Cod sursa(job #3208434)

Utilizator bogdibogdiAndrei Bogdan bogdibogdi Data 28 februarie 2024 17:12:04
Problema Rj Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.34 kb
#include <iostream>
#include <fstream>
#include <queue>

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();
    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]) fout<<v[i][j]<<" "<<i<<" "<<j;
        }
    }
    return 0;
}