Cod sursa(job #1737465)

Utilizator Mircea_DonciuDonciu Mircea Mircea_Donciu Data 4 august 2016 10:36:43
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.15 kb
#include <fstream>
#include  <queue>
using namespace std;
queue < pair<int,int> > q;
int m,n,i,j,ir,jr,jj,ij,x,y,k,mini,z,t,b[105][105],d[105][105];
int v[105][105];
char c;
int main()
{
    ifstream f("rj.in");
    ofstream g("rj.out");
    int dx[]={-1,-1,-1,0,1,1,1,0};
    int dy[]={-1,0,1,1,1,0,-1,-1};
    f>>n>>m;
    for(i=1; i<=n; i++)
    for(j=1; j<=m; j++)
    {
        b[i][j]=20000;
        d[i][j]=20000;
    }
    mini=20000;
    f.get();
    for(i=1; i<=n; i++)
    {
        f.get(c);
        for(j=1; c!='\n'; j++)
        {
            if(c=='X')
                v[i][j]=1;
            else
            if(c=='R')
            {
                ir=i;
                jr=j;
            }
            else
            if(c=='J')
            {
                ij=i;
                jj=j;
            }
            f.get(c);
        }
    }
    for(i=0; i<=n+1; i++)
    {
        v[i][0]=1;
        v[i][m+1]=1;
    }
    for(i=0; i<=m+1; i++)
    {
        v[0][i]=1;
        v[n+1][i]=1;
    }
    b[ir][jr]=0;
    q.push(make_pair(ir,jr));
    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(v[x][y]!=1&&b[x][y]>b[i][j]+1)
            {
                b[x][y]=b[i][j]+1;
                q.push(make_pair(x, y));
            }
        }
    }
    // al doile Lee
    d[ij][jj]=0;
    q.push(make_pair(ij,jj));
    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(v[x][y]!=1&&d[x][y]>d[i][j]+1)
            {
                d[x][y]=d[i][j]+1;
                q.push(make_pair(x, y));
            }
        }
    }
    for(i=1; i<=n; i++)
    for(j=1; j<=m; j++)
    {
        if(b[i][j]==d[i][j]&&b[i][j]<mini&&v[i][j]==0)
        {
            mini=d[i][j];
            z=i;
            t=j;
        }
    }
    g<<mini+1<<" "<<z<<" "<<t<<'\n';
    f.close(); g.close();
    return 0;
}