Cod sursa(job #2007997)

Utilizator maria15Maria Dinca maria15 Data 4 august 2017 20:46:15
Problema A+B Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.96 kb
#include <fstream>
#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(s, m);
        for(j=1;j<=m;j++){
            if(s[j]=='X')
                v[i][j]=-1;
            if(s[j]=='R'){
                ir=i;
                jr=j;
                v[i][j]=0;
            }
            if(s[j]=='J'){
                ij=i;
                jj=j;
                v[i][j]=0;
            }
            if(s[j] == ' ')
                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 && v[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++;
    }
    sort(in+1, in+sol+1);
    /*fout<<in[1].first<<" "<<in[1].second<<" "<<gasit<<" "<<ok;*/

    return 0;
}