Cod sursa(job #1735342)

Utilizator andreigeorge08Sandu Ciorba andreigeorge08 Data 29 iulie 2016 15:58:17
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.6 kb
#include <fstream>
#include <cstring>
#include <queue>
#define inf 10000000
using namespace std;
ifstream fin("rj.in");
ofstream fout("rj.out");
char a[105];
int n,m,b[105][105],xs,ys,xd,yd,c[105][105],d[105][105];
queue<pair<int,int> >q;
void Citire()
{
    int i,x,ii,jj;
    fin>>n>>m;
    ii=jj=0;
    while(fin.getline(a,105))
    {
        x=strlen(a);
        for(i=0;i<x;i++)
        {
            if(a[i]=='X')
              b[ii][jj]=-1;
            else if(a[i]=='R')
            {
                xs=ii;
                ys=jj;
                b[ii][jj]=1;
            }
            else if(a[i]==' ')
             b[ii][jj]=1;
            else if(a[i]=='J')
            {
                xd=ii;
                yd=jj;
                b[ii][jj]=1;
            }
            jj++;
        }
        ii++;
        jj=1;
    }
}
void Bordare()
{
    int i;
    for(i=0;i<=m+1;i++)
        b[0][i]=b[n+1][i]=-1;
    for(i=0;i<=n+1;i++)
        b[i][0]=b[i][m+1]=-1;
}
void Initializare()
{
    int i,j;
    for(i=1;i<=n;i++)
        for(j=1;j<=m;j++)
            c[i][j]=d[i][j]=inf;
}
void LeeRomeo()
{
    int i,j,x,y,k;
   int dx[10]={0,0,-1,1,-1,1,-1,1};
    int dy[10]={-1,1,0,0,-1,1,1,-1};
    q.push(make_pair(xs,ys));
    c[xs][ys]=1;
    while(!q.empty())
    {
        i=q.front().first;
        j=q.front().second;
        q.pop();
        for(k=0;k<8;k++)
        {
            x=i+dx[k];
            y=j+dy[k];
            if(b[x][y]!=-1 and c[x][y]>c[i][j]+1)
            {
                c[x][y]=c[i][j]+1;
                q.push(make_pair(x,y));
            }
        }
    }
}
void LeeJulieta()
{
    int i,j,x,y,k;
   int dx[10]={0,0,-1,1,-1,1,-1,1};
    int dy[10]={-1,1,0,0,-1,1,1,-1};
    q.push(make_pair(xd,yd));
    d[xd][yd]=1;
    while(!q.empty())
    {
        i=q.front().first;
        j=q.front().second;
        q.pop();
        for(k=0;k<8;k++)
        {
            x=i+dx[k];
            y=j+dy[k];
            if(b[x][y]!=-1 and d[x][y]>d[i][j]+1)
            {
                d[x][y]=d[i][j]+1;
                q.push(make_pair(x,y));
            }
        }
    }
}
inline void Rezolvare()
{
    int i,j,minim=inf,pozitie,pozitie1;
    for(i=1;i<=n;i++)
        for(j=1;j<=m;j++)
        if(c[i][j]==d[i][j] and minim>c[i][j])
    {
        minim=c[i][j];
        pozitie=i;
        pozitie1=j;
    }
    fout<<minim<<" "<<pozitie<<" "<<pozitie1<<"\n";
}
int main()
{
    Citire();
    Bordare();
    Initializare();
    LeeRomeo();
    LeeJulieta();
    Rezolvare();
    return 0;
}