Cod sursa(job #3149877)

Utilizator Stormtrooper-007Vartic Rihard Stormtrooper-007 Data 13 septembrie 2023 11:23:36
Problema Rj Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.17 kb
#include <bits/stdc++.h>

using namespace std;
bool v[102][102];
int inf=1e9;
int dist[102][102];
int dist2[102][102];
int diri[8]={1,0,-1,0,1,-1,-1,1};
int dirj[8]={0,1,0,-1,1,-1,1,-1};
int main()
{
    ifstream cin("rj.in");
    ofstream cout("rj.out");
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            dist[i][j]=inf;
            dist2[i][j]=inf;
        }
    }
    for(int i=1;i<=n;i++)
    {
        v[i][0]=1;
        v[i][m+1]=1;
    }
    for(int j=2;j<=m;j++)
    {
        v[n+1][j]=1;
        v[0][j]=1;
    }
    v[n+1][m+1]=1;
    v[0][m+1]=1;
    v[n+1][0]=1;
    v[0][0]=1;
    cin.get();
    int inc1,inc2,en1,en2;
    for(int i=1;i<=n;i++)
    {char c;
        for(int j=1;j<=m;j++)
        {

            c=cin.get();

            if(c=='X')
            {
                v[i][j]=1;
            }
            if(c=='R')
            {
                inc1=i;
                inc2=j;
               // cout<<i<<" "<<j<<'\n';
            }
            if(c=='J')
            {
                en1=i;
                en2=j;
            }
        }
        if(c!='\n')
        cin.get();
    }
    //cin>>inc1>>inc2>>en1>>en2;
    queue<pair<int,int>>q;
    q.push({inc1,inc2});
    dist[inc1][inc2]=1;
    while(!q.empty())
    {
        int a=q.front().first;
        int b=q.front().second;
        q.pop();
        //v[a][b]=1;
        for(int i=0;i<8;i++)
        {
            if(v[a+diri[i]][b+dirj[i]]==0 && dist[a][b]+1<dist[a+diri[i]][b+dirj[i]])
            {
                dist[a+diri[i]][b+dirj[i]]=dist[a][b]+1;
                q.push({a+diri[i],b+dirj[i]});
            }
        }
    }    ////////////////////////////////////////////////////////////////////////////////////////////////
    q.push({en1,en2});
    dist2[en1][en2]=1;
    while(!q.empty())
    {
        int a=q.front().first;
        int b=q.front().second;
        q.pop();
        //v[a][b]=1;
        for(int i=0;i<8;i++)
        {
            if(v[a+diri[i]][b+dirj[i]]==0 && dist2[a][b]+1<dist2[a+diri[i]][b+dirj[i]])
            {
                dist2[a+diri[i]][b+dirj[i]]=dist2[a][b]+1;
                q.push({a+diri[i],b+dirj[i]});
            }
        }
    }
    int ans=2e9,c1,c2;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            if(dist[i][j]==dist2[i][j] && dist[i][j]!=0)
            {
                if(ans>dist[i][j])
                {
                    ans=dist[i][j];
                    c1=i;
                    c2=j;
                }
            }
            //cout<<v[i][j]<<" ";
        }
       // cout<<'\n';
    }
    //cout<<'\n';
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            if(dist[i][j]==dist2[i][j] && dist[i][j]!=0)
            {
                if(ans>dist[i][j])
                {
                    ans=dist[i][j];
                    c1=i;
                    c2=j;
                }
            }
           // cout<<dist2[i][j]<<" ";
        }
        //cout<<'\n';
    }

    cout<<ans<<" "<<c1<<" "<<c2;
    return 0;
}