Cod sursa(job #1118667)

Utilizator andreiulianAndrei andreiulian Data 24 februarie 2014 12:33:34
Problema Rj Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.12 kb
#include<iostream>
#include<fstream>
#include<cstring>
using namespace std;
int N,M,l1,c1,l2,c2,a[102][102];
struct punct{int l,c;} v[10001];
int p,u,ok,lmin=100,cmin=100,k,r;
int dl[]={0,-1,-1,0,1,1, 1, 0,-1},
    dc[]={0, 0, 1,1,1,0,-1,-1,-1};
char m[102][102];
void gaseste(int l,int c,int x);
int main()
{
    ifstream in("rj.in");
    ofstream out("rj.out");
    int i,j,t,r;
    char *q;
    in>>N>>M;
    in.getline(m[0],10);
    for(i=1;i<=N;i++)
    {
        in.getline(m[i]+1,101);
        q=strchr(m[i]+1,'R');
        m[i][0]=m[i][M+1]='X';
        if(q)
        {
            l1=i;
            c1=q-m[i];
        }
        q=strchr(m[i]+1,'J');
        if(q)
        {
            l2=i;
            c2=q-m[i];
        }
    }
    for(i=0;i<=M+1;i++)
    {
        m[0][i]='X';
        m[N+1][i]='X';
    }
    //incepe lee

    a[l1][c1]=1;
    p=u=1;
    v[p].l=l1;
    v[p].c=c1;
    ok=0;
    int lc,cc,lv,cv,d;
    while(p<=u && ok==0)
    {
        lc=v[p].l;
        cc=v[p].c;
        if(lc==l2 && cc==c2) {ok=1;t=a[lc][cc]/2+1; out<<t<<' ';}
        else
        {
            for(d=1;d<=8;d++)
            {
                lv=lc+dl[d];
                cv=cc+dc[d];
                if(m[lv][cv]!='X')
                {
                    if(a[lv][cv]>a[lc][cc]+1 || a[lv][cv]==0)
                    {
                    u++;
                    v[u].l=lv;
                    v[u].c=cv;
                    a[lv][cv]=a[lc][cc]+1;
                    }
                }
            }
        }
        p++;
    }
    k=0;
    gaseste(l2,c2,t);
    out<<lmin<<' '<<cmin<<'\n';
}
void gaseste(int l,int c,int x)
{
    int i,lv,cv;
    r=a[l][c];
    for(i=1;i<=8;i++)
    {
        lv=l+dl[i];
        cv=c+dc[i];
        if(a[lv][cv]==r-1)
        {
            if(a[lv][cv]==x)
            {
                if(lv<lmin || (lv==lmin && cv<cmin))
                {
                    lmin=lv;
                    cmin=cv;
                    k=1;
                }
            }
            else
                gaseste(lv,cv,x);
        }
    }
}