Cod sursa(job #2586068)

Utilizator Catalinu23Gavrila Catalin Catalinu23 Data 19 martie 2020 18:15:14
Problema Rj Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.75 kb
#include <bits/stdc++.h>

using namespace std;
ifstream fin("rj.in");
ofstream fout("rj.out");
int n,m,rlin,rcol,jlin,jcol;
char ch[205];
short a[105][105],b[105][105],c[105][105];
short dx[]={0,0,-1,-1,-1,1,1,1};
short dy[]={-1,1,0,-1,1,0,-1,1};
struct poz
{
    int x;
    int y;
};
queue<poz> q;
void Bordare()
{
    for(int i=0;i<=m+1;i++)
    {
        a[0][i]=a[n+1][i]=1;
    }
    for(int i=0;i<=n+1;i++)
    {
        a[i][0]=a[i][m+1]=1;
    }
}
void Citire()
{
    fin>>n>>m;
    fin.getline(ch,200);
    for(int i=1;i<=n;i++)
    {
        fin.getline(ch,200);
        for(int j=0;j<=m;j++)
        {
            if(ch[j]=='X')
            {
                a[i][j+1]=1;
            }
            else if(ch[j]=='R')
            {
                rlin=i;
                rcol=j+1;
            }
            else if(ch[j]=='J')
            {
                jlin=i;
                jcol=j;
            }
        }
    }
}
void Lee1(int xx,int yy)
{
    poz w1,w2;
    w1.x=xx;
    w1.y=yy;
    b[xx][yy]=1;
    while(!q.empty())
    {
        q.pop();
    }
    q.push(w1);
    while(!q.empty())
    {
        w1=q.front();
        q.pop();
        int x=w1.x,y=w1.y;
        for(int k=0;k<=7;k++)
        {
            int i=x+dx[k],j=y+dy[k];
            if(a[i][j]==0&&(b[i][j]==0||b[i][j]>b[x][y]+1))
            {
                b[i][j]=b[x][y]+1;
                w2.x=i;
                w2.y=j;
                q.push(w2);
            }
        }
    }
}
void Lee2(int xx,int yy)
{
    poz w1,w2;
    w1.x=xx;
    w1.y=yy;
    c[xx][yy]=1;
    while(!q.empty())
    {
        q.pop();
    }
    q.push(w1);
    while(!q.empty())
    {
        w1=q.front();
        q.pop();
        int x=w1.x,y=w1.y;
        for(int k=0;k<=7;k++)
        {
            int i=x+dx[k],j=y+dy[k];
            if(a[i][j]==0&&(c[i][j]==0||c[i][j]>c[x][y]+1))
            {
                c[i][j]=c[x][y]+1;
                w2.x=i;
                w2.y=j;
                q.push(w2);
            }
        }
    }
}
void Rezolvare()
{
    int minim=10000,lmin,cmin;
    Lee1(rlin,rcol);
    Lee2(jlin,jcol);
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            if(b[i][j]!=0&&b[i][j]==c[i][j]&&b[i][j]<minim)
            {
                minim=b[i][j];
                lmin=i;
                cmin=j;
            }
        }
    }
    fout<<minim<<" "<<lmin<<" "<<cmin<<" ";;
}
int main()
{
    Citire();
    Bordare();
    Rezolvare();
    /*for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            cout<<b[i][j]<<" ";
        }
        cout<<"\n";
    }
    cout<<"-------------------------------------\n";
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            cout<<c[i][j]<<" ";
        }
        cout<<"\n";
    }*/
    return 0;
}