Cod sursa(job #1474526)

Utilizator alexandra_udristoiuUdristoiu Alexandra Maria alexandra_udristoiu Data 22 august 2015 10:29:10
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.34 kb
#include<fstream>
#include<cstring>
using namespace std;
int n, m, p, u, i, j, C, L, ii1, jj1, ii2, jj2, ii, jj, iv, jv, d;
char a[105][105], s[105];
int e[105][105], f[105][105], c[2][102*102];
int di[8] = {-1, 1, 0, 0, -1, -1, 1, 1};
int dj[8] = {0, 0, -1, 1, -1, 1, -1, 1};
ifstream fin("rj.in");
ofstream fout("rj.out");
int main(){
    fin>> n >> m;
    for(i = 1; i <= n; i++){
        fin.get();
        fin.get(s, 105);
        j = strlen(s);
        while(j < m){
            s[j] = ' ';
            j++;
        }
        for(j = 1; j <= m; j++){
            a[i][j] = s[j - 1];
            if(a[i][j] == 'R'){
                ii1 = i;
                jj1 = j;
                e[i][j] = 1;
            }
            else{
                if(a[i][j] == 'J'){
                    ii2 = i;
                    jj2 = j;
                    f[i][j] = 1;
                }
                else{
                    if(a[i][j] == 'X'){
                        e[i][j] = f[i][j] = -1;
                    }
                }
            }
        }
    }
    p = u = 1;
    c[0][1] = ii1;
    c[1][1] = jj1;
    while(p <= u){
        ii = c[0][p];
        jj = c[1][p];
        for(d = 0; d < 8; d++){
            iv = ii + di[d];
            jv = jj + dj[d];
            if(iv >= 1 && iv <= n && jv >= 1 && jv <= m && e[iv][jv] == 0){
                e[iv][jv] = e[ii][jj] + 1;
                u++;
                c[0][u] = iv;
                c[1][u] = jv;
            }
        }
        p++;
    }

    p = u = 1;
    c[0][1] = ii2;
    c[1][1] = jj2;
    while(p <= u){
        ii = c[0][p];
        jj = c[1][p];
        for(d = 0; d < 8; d++){
            iv = ii + di[d];
            jv = jj + dj[d];
            if(iv >= 1 && iv <= n && jv >= 1 && jv <= m && f[iv][jv] == 0){
                f[iv][jv] = f[ii][jj] + 1;
                u++;
                c[0][u] = iv;
                c[1][u] = jv;
            }
        }
        p++;
    }

    e[0][0] = f[0][0] = 1000000;
    for(i = 1; i <= n; i++){
        for(j = 1; j <= m; j++){
            if(e[i][j] == f[i][j] && e[i][j] > 0){
                if(e[i][j] < e[L][C]){
                    L = i;
                    C = j;
                }
            }
        }
    }
    fout<< e[L][C] <<" "<< L <<" "<< C <<"\n";
    return 0;
}