Cod sursa(job #2008094)

Utilizator maria15Maria Dinca maria15 Data 5 august 2017 12:17:16
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.44 kb
#include <fstream>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <iostream>

using namespace std;

int n, i, j, m, p, u, sol, ir, jr, ij, jj, iv, jv, ic, jc, gasit, v[102][102], v2[102][102], d;
short di[] = {-1, -1, -1,  0, 0,  1,  1, 1};
short dj[] = {-1,  0,  1, -1, 1, -1,  0, 1};
char ch, s[103];
pair <short, short> in[1000];

int c[3][10003], ok;

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

int main(){
    fin>>n>>m;

    for(i=1;i<=n;i++){
        fin.get();
        fin.get(s, 110);
        for(j=1;j<=m;j++){
            if(s[j-1]=='X')
                v[i][j]=-1;
            if(s[j-1]=='R'){
                ir=i;
                jr=j;
                v[i][j]=0;
            }
            if(s[j-1]=='J'){
                ij=i;
                jj=j;
                v[i][j]=0;
            }
            if(s[j-1] == ' ')
                v[i][j]=0;
            v2[i][j]=v[i][j];
        }
    }
    // construiesc drumul de la romeo la julieta
   /* for(i=1;i<=n;i++){
        for(j=1;j<=m;j++)
            fout<<v[i][j]<<" ";
        fout<<endl;
    }*/
    p=u=1;
    c[0][1]=ir;
    c[1][1]=jr;
    v[ir][jr]=1;
    while(p<=u){
        ic=c[0][p];
        jc=c[1][p];
        for(d=0;d<8;d++){
            iv=ic+di[d];
            jv=jc+dj[d];
            if(iv>=1 && iv<=n && jv>=1 && jv<=m && v[iv][jv] == 0){
                u++;
                c[0][u]=iv;
                c[1][u]=jv;
                v[iv][jv]=v[ic][jc]+1;
            }
        }
        p++;
    }

    // construiesc drumul de la julieta la romeo

    p=u=1;
    c[0][1]=ij;
    c[1][1]=jj;
    v2[ij][jj]=1;

    while(p<=u){
        ic=c[0][p];
        jc=c[1][p];
        for(d=0;d<8;d++){
            iv=ic+di[d];
            jv=jc+dj[d];
            if(iv>=1 && iv<=n && jv>0 && jv<=m && v2[iv][jv] == 0){
                u++;
                c[0][u]=iv;
                c[1][u]=jv;
                v2[iv][jv]=v2[ic][jc]+1;
                /*
                if(v[iv][jv] == v2[iv][jv]){    //daca se pot intalni in (iv, jv)
                    if(ok==0){              //daca nu s-au mai putut intalni niciunde pana acum
                        in[++sol].first=iv;
                        in[sol].second=jv;
                        gasit=v[iv][jv];
                        ok=1;
                    }
                    else
                        if(v2[iv][jv] == gasit){    // doar daca sunt la acelasi timp de intalnire precum cel deja gasit
                            in[++sol].first=iv;
                            in[sol].second=jv;
                        }
                        else{               // am gasit deja un loc de intalnire cu timp mai bun
                            p=u+1;
                            break;          // DECI NU MAI ARE ROST SA CAUT
                        }
                }
                */
            }
        }
        p++;
    }
    int minim = 10010;
    int iminim, jminim;
    for (i=1;i<=n;i++)
        for (j=1;j<=m;j++)
            if (v[i][j] == v2[i][j] && v[i][j] > 0) {
                if (v[i][j] < minim) {
                    minim = v[i][j];
                    iminim = i;
                    jminim = j;
                }
//                fout<<i<<" "<<j<<" "<<v[i][j];
//                return 0;
            }

//    sort(in+1, in+sol+1);
    fout<<minim<<" "<<iminim<<" "<<jminim;

    return 0;
}