Cod sursa(job #678610)

Utilizator shuleavSulea Vlad shuleav Data 11 februarie 2012 23:46:21
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.1 kb
#include <fstream>
#include <deque>
#define M 102
using namespace std;
ifstream f("rj.in");
ofstream g("rj.out");
int dx[8]= {1,-1,1,0,-1,-1,0,1};
int dy[8]= {0,0,1,-1,-1,1,1,-1};
struct poz
{
    int l,c;
};
poz aux;
deque<poz> D;
int i,j,n,m,a[M][M],len,b[M][M],bb[M][M],ir,jr,ij,jj,d,mini,soli,solj;
string s;
void pushr(int l, int c, int v)
{
    if(l<1 || l>n) return;
    if(c<1 || c>m) return;
    if(a[l][c]<0) return;
    if(b[l][c]>=0 && v>=b[l][c]) return;
    b[l][c]=v;
    aux.l=l;
    aux.c=c;
    D.push_back(aux);
}
void pushj(int l, int c, int v)
{
    if(l<1 || l>n) return;
    if(c<1 || c>m) return;
    if(a[l][c]<0) return;
    if(bb[l][c]>=0 && v>=bb[l][c]) return;
    bb[l][c]=v;
    aux.l=l;
    aux.c=c;
    D.push_back(aux);
}
int main()
{
    f>>n>>m;
    f.get();
    for(i=1; i<=n; i++)
    {
        getline(f,s);
        len=s.size();
        for(j=0; j<len; j++)
        {
            if(s[j]=='X')a[i][j+1]=-1;
            if(s[j]==' ')a[i][j+1]=0;
            if(s[j]=='R') ir=i,jr=j+1;
            if(s[j]=='J') ij=i,jj=j+1;
        }
    }
    for(i=1; i<=n; i++)
        for(j=1; j<=m; j++) b[i][j]=-1;
    b[ir][jr]=1;
    aux.l=ir;
    aux.c=jr;
    D.push_back(aux);
    while(!D.empty())
    {
        aux=D.front();
        D.pop_front();
        i=aux.l;
        j=aux.c;
        for(d=0; d<8; d++)
            pushr(i+dx[d],j+dy[d],b[i][j]+1);
    }
    D.clear();
    for(i=1; i<=n; i++)
        for(j=1; j<=m; j++) bb[i][j]=-1;
    bb[ij][jj]=1;
    aux.l=ij;
    aux.c=jj;
    D.push_back(aux);
    while(!D.empty())
    {
        aux=D.front();
        D.pop_front();
        i=aux.l;
        j=aux.c;
        for(d=0; d<8; d++)
            pushj(i+dx[d],j+dy[d],bb[i][j]+1);
    }
    mini=1000000;
    for(i=1; i<=n; i++)
        for(j=1; j<=m; j++)
            if(b[i][j]!=-1 && b[i][j]!=0 && b[i][j]==bb[i][j] && b[i][j]<mini)
            {
                mini=b[i][j];
                soli=i;
                solj=j;
            }
    g<<mini<<' '<<soli<<' '<<solj<<' '<<'\n';
    return 0;
}