Cod sursa(job #2041099)

Utilizator DavidDragulinDragulin David DavidDragulin Data 16 octombrie 2017 20:49:02
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.99 kb
#include <bits/stdc++.h>

using namespace std;
ifstream fin("rj.in");
ofstream fout("rj.out");
queue <pair <int,int> > q;
int vx[]= {-1,-1,0,1,1,1,0,-1},vy[]= {0,1,1,1,0,-1,-1,-1};
int n,m,a[109][109],b[109][109],c[109][109],x1,x2,Y1,y2,x,y,nr,i,j;
char uless,ch;
int main()
{
    fin>>n>>m;
    fin>>noskipws>>uless;
    for(i=1; i<=n; i++)
    {
        for(j=1; j<=m+1; j++)
        {
            fin>>noskipws>>ch;
            if(ch=='X')
                a[i][j]=1;
            else if(ch=='R')
                x1=i,Y1=j,a[x1][Y1]=1;
            else if(ch=='J')
                x2=i,y2=j,a[x2][y2]=1;
            if(ch=='\n')
                j=m+2;
        }
    }
    for(i=0; i<=n; i++)
        a[i][0]=a[i][m+1]=-1;
    for(i=0; i<=m; i++)
        a[0][i]=a[n+1][i]=-1;
    q.push(make_pair(x1,Y1));
    while(!q.empty())
    {
        x=q.front().first;
        y=q.front().second;
        q.pop();
        for(i=0; i<8; i++)
        {
            if(a[x+vx[i]][y+vy[i]]==0)
                if(b[x+vx[i]][y+vy[i]]==0||b[x+vx[i]][y+vy[i]]>b[x][y]+1)
                {
                    b[x+vx[i]][y+vy[i]]=b[x][y]+1;
                    q.push(make_pair(x+vx[i],y+vy[i]));
                }
        }
    }
    q.push(make_pair(x2,y2));
    while(!q.empty())
    {
        x=q.front().first;
        y=q.front().second;
        q.pop();
        for(i=0; i<8; i++)
        {
            if(a[x+vx[i]][y+vy[i]]==0)
                if(c[x+vx[i]][y+vy[i]]==0||c[x+vx[i]][y+vy[i]]>c[x][y]+1)
                {
                    c[x+vx[i]][y+vy[i]]=c[x][y]+1;
                    q.push(make_pair(x+vx[i],y+vy[i]));
                }
        }
    }
    nr=INT_MAX;
    for(i=1;i<=n;i++)
        for(j=1;j<=m;j++)
        {
            if(b[i][j]>0&&b[i][j]==c[i][j])
                if(b[i][j]<nr)
                {
                    nr=b[i][j];
                    x=i,y=j;
                }
        }
    fout<<nr+1<<" "<<x<<" "<<y;

    return 0;
}