Cod sursa(job #2644090)

Utilizator VladutzPredoiVlad Predoi VladutzPredoi Data 23 august 2020 13:02:57
Problema Rj Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.91 kb
#include <iostream>
#include <fstream>
#include <queue>
using namespace std;


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

int n,m,xj,yj,xr,yr;
char ch[205];
int a[105][105],rr[105][105],jj[105][105];
int dx[]={-1,-1,0,1,1,1,0,-1};
int dy[]={0,1,1,1,0,-1,-1,-1};

queue < pair < int,int > >Q;

void read()
{
    fin>>n>>m;
    fin.get();
    for(int i=1;i<=n;i++)
    {
        fin.getline(ch+1,200);
        for(int j=1;j<=m;j++)
        {
            if(ch[j]==' ')
                a[i][j]=0;
            else if(ch[j]=='J')
            {
                xj=i;
                yj=j;
            }
            else if(ch[j]=='R')
            {
                xr=i;
                yr=j;
            }
            else
                a[i][j]=1;
        }

    }
}

bool ok(int i,int j)
{
    return (1<=i && i<=n && 1<=j && j<=m && a[i][j]!=1);
}

void lee(int xst,int yst,int d[105][105])
{
    d[xst][yst]=1;
    Q.push(make_pair(xst,yst));
    while(!Q.empty())
    {
        int i=Q.front().first;
        int j=Q.front().second;
        Q.pop();
        for(int dir=0;dir<8;dir++)
        {
            int i_next=i+dx[dir];
            int j_next=j+dy[dir];
            if(ok(i_next,j_next) && (d[i_next][j_next]==0 || d[i_next][j_next]>d[i][j]+1))
            {
                 d[i_next][j_next]=d[i][j]+1;
                 Q.push(make_pair(i_next,j_next));
            }
        }

    }
}

void solve()
{
    lee(xj,yj,jj);
    lee(xr,yr,rr);
    int minim=1000000,xsol,ysol;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            if(jj[i][j]==rr[i][j] && jj[i][j]<minim && jj[i][j]!=0)
            {
                minim=jj[i][j];
                xsol=i;
                ysol=j;
            }
        }
    }
    fout<<minim<<" "<<xsol<<" "<<ysol<<"\n";
}
int main()
{
    read();
    solve();
    return 0;
}