Cod sursa(job #3208431)

Utilizator bogdibogdiAndrei Bogdan bogdibogdi Data 28 februarie 2024 17:04:30
Problema Rj Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.05 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[]={0,0,-1,1},dj[]={1,-1,0,0};

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<4;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;
    }
    fout<<(v[ifinal][jfinal]-1)/2<<" ";
}

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<4;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;
    }
}

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<<i<<" "<<j;
        }
    }
    return 0;
}