Cod sursa(job #1901177)

Utilizator oana_fOana Fiat oana_f Data 3 martie 2017 19:40:01
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.15 kb
#include <fstream>
#include <queue>

using namespace std;

ifstream fin("rj.in");
ofstream fout("rj.out");

int n,m;
int ro[101][101], ju[101][101];

int di[]={-1,-1,-1,0,0,1,1,1};
int dj[]={-1,0,1,-1,1,-1,0,1};

queue<int> ri, rj, ji, jj;

void intalnirea(int &iint, int &jint, int &minint) {
    int pri,prj,mir,pji,pjj,mij,i,vi,vj;
    while(!ri.empty() && !ji.empty()) {
            pri=ri.front();
            prj=rj.front();
            mir=ro[pri][prj];
            while(ro[pri][prj]==mir) {
                ri.pop();
                rj.pop();
                for(i=0;i<8;i++) {
                    vi=pri+di[i];
                    vj=prj+dj[i];
                    if(vi>0 && vi<=n && vj>0 && vj<=m)
                        if(ro[vi][vj]==0) {
                            ro[vi][vj]=mir+1;
                            ri.push(vi);
                            rj.push(vj);
                        }
                }
                pri=ri.front();
                prj=rj.front();
            }

            pji=ji.front();
            pjj=jj.front();
            mij=ju[pji][pjj];
            while(ju[pji][pjj]==mij) {
                ji.pop();
                jj.pop();
                for(i=0;i<8;i++) {
                    vi=pji+di[i];
                    vj=pjj+dj[i];
                    if (vi>0 && vi<=n && vj>0 && vj<=m)
                        if(ju[vi][vj]==0) {
                            if(ro[vi][vj]==mij+1) {
                                iint=vi;
                                jint=vj;
                                minint=mij+1;
                                return;
                            } else {
                                ju[vi][vj]=mij+1;
                                ji.push(vi);
                                jj.push(vj);
                            }
                        }
                }
                pji=ji.front();
                pjj=jj.front();
            }
        }
}


int main()
{
    int i,j,iint, jint, mint;
    char c;
    fin>>n>>m;
    fin.get();
    for(i=1;i<=n;i++){
        for(j=1;j<=m;j++) {
            fin.get(c);
            if(c=='X') {
                ro[i][j]=-1;
                ju[i][j]=-1;
            } else
                if(c==' ') {
                    ro[i][j]=0;
                    ju[i][j]=0;
                } else
                    if(c=='R') {
                        ro[i][j]=1;
                        ju[i][j]=0;
                        ri.push(i);
                        rj.push(j);
                    } else if(c=='J') {
                        ro[i][j]=0;
                        ju[i][j]=1;
                        ji.push(i);
                        jj.push(j);
                    }
        }
        fin.get();
    }
    intalnirea(iint, jint, mint);
    fout<<mint<<" "<<iint<<" "<<jint;
    /*fout<<"Romeo"<<endl;
    for (i=1;i<=n;i++) {
        for(j=1;j<=m;j++)
            fout<<ro[i][j]<<" ";
        fout<<endl;
    }
    fout<<"Julieta"<<endl;
    for (i=1;i<=n;i++) {
        for(j=1;j<=m;j++)
            fout<<ju[i][j]<<" ";
        fout<<endl;
    }*/


    return 0;
}