Cod sursa(job #1612545)

Utilizator Flavius08Flavius Aga Flavius08 Data 24 februarie 2016 21:57:21
Problema Rj Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.39 kb
#include <fstream>
#include <sstream>
#define nMax 100
#define mMax 100
#define DEBUG 0
#define DB if(DEBUG)
using namespace std;

int oras[nMax+1][mMax+1],N,M,dcrt=0,vmax=nMax*mMax+1;
int X=vmax+'X',R=vmax+'R',J=vmax+'J',  Spatiu=vmax+' ';
int iR, jR, iJ, jJ, iIntalnire=X, jIntalnire=X, tminDrum;
int di[]={1,0,-1,-1,-1,0,1,1};
int dj[]={-1,-1,-1,0,1,1,1,0};

void citiremat(char numefis[])
{
    int i,j,k=0;
    char cc;
    string  linie;
    ifstream in(numefis);

    getline(in,linie);
    stringstream ssin(linie);
    ssin>>N>>M;
    DB printf("N=%d M=%d\n",N,M);
    for(i=1;i<=N;i++){
        getline(in,linie);
        for(j=1;j<=M;j++)
        {
            cc=linie[j-1];
            if(cc==0 || cc=='\r' || cc=='\n') break;
            k++;
            DB printf("%c",cc==' '?'.':cc);
            oras[i][j]=vmax+toupper(cc);
            if(oras[i][j]==R) {
                iR=i;
                jR=j;
            }
            else if(oras[i][j]==J) {
                iJ=i;
                jJ=j;
            }
        }
        DB printf("\n");
    }
     DB printf(" iR=%d jR=%d iJ=%d jJ=%d k=%d ********\n", iR, jR, iJ, jJ, k);

}
void afismat(char * numefis)
{
    ofstream out(numefis);
    int i,j;
    DB printf("\n");
    for(i=1;i<=N;i++)
    {
        out<<endl;
        DB printf("\n");
        for(j=1;j<=M;j++) {
           out<<oras[i][j]<<" ";
           DB printf("%c ",oras[i][j]>vmax?oras[i][j]-vmax: oras[i][j]+'0');
        }
    }
}

void drecurs(int i, int j, int d){
    int dcrt=d;
    int k, iv, jv, oc ;
    for(k=0;k<8;k++){
        iv=i+di[k];
        if(iv<1||iv>N) continue;
        jv=j+dj[k];
        if(jv<1||jv>M) continue;
        oc=oras[iv][jv];
        if(oc==X || oc==R || oc==J) continue;
        if(oc > dcrt) {
                oras[iv][jv]= dcrt;
                drecurs(iv,jv, dcrt+1);
        }
    }
}

int timpminim(int i, int j){
    int k, iv, jv, oc,tmin=X ;
    for(k=0;k<8;k++){
        iv=i+di[k];
        if(iv<1||iv>N) continue;
        jv=j+dj[k];
        if(jv<1||jv>M) continue;
        oc=oras[iv][jv];
        if(oc==X || oc==R || oc==J) continue;
        if(oc < tmin) {
                tmin=oc;
        }
    }
    return tmin;
}

void cautaPunctDeIntalnire(int i, int j, int tstart,int tstop){
    int k, iv, jv, oc;
    DB printf("\ni=%d j=%d tstart=%d tstop=%d", i,j,tstart, tstop);
    for(k=0;k<8;k++){
        iv=i+di[k];
        if(iv<1||iv>N) continue;
        jv=j+dj[k];
        if(jv<1||jv>M) continue;
        oc=oras[iv][jv];
        if(oc==X || oc==R || oc==J) continue;
        if(oc == tstop) {
            if(iv<iIntalnire) {
                iIntalnire=iv;
                jIntalnire=jv;
            }
            if (iv==iIntalnire && jv<jIntalnire) {
                        jIntalnire=jv;
            }
            continue;
        }
        if(oc==tstart)
            cautaPunctDeIntalnire(iv,jv, tstart-1,tstop);
    }
}

int main()
{

    citiremat("rj.in");
    DB afismat("rj.out");

    drecurs(iR, jR, 1);
    DB afismat("rj.out");

    tminDrum=timpminim(iJ,jJ);
    DB printf("\ntmin=%d",tminDrum);

    cautaPunctDeIntalnire(iJ,jJ,tminDrum,(tminDrum+1)/2);
    DB printf(" Intalnire=(%d, %d)",iIntalnire,jIntalnire);

    ofstream out("rj.out");
    out<<tminDrum<< " " <<iIntalnire<<" " <<jIntalnire<<endl;
    return 0;
}