Cod sursa(job #2077693)

Utilizator andreicoman299Coman Andrei andreicoman299 Data 28 noiembrie 2017 14:27:30
Problema Rj Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.17 kb
#include <bits/stdc++.h>

char v[101][101];
int t1[101][101];
int t2[101][101];
int q[100 * 100 + 1][2];
int dir[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};

int main(){
    FILE*fi,*fo;
    fi = fopen("rj.in","r");
    fo = fopen("rj.out","w");

    int n, m;
    fscanf(fi,"%d%d", &n, &m);
    int ri, rj, ji, jj;
    char c = fgetc(fi);
    for(int i = 1; i <= n; i++){
        while(c != ' ' && c != 'X' && c != 'R' && c !='J')
            c = fgetc(fi);
        for(int j = 1; j <= m; j++){
            v[i][j] = c;
            if(c == 'R'){
                ri = i;
                rj = j;
            }
            else if(c == 'J'){
                ji = i;
                jj = j;
            }
            c = fgetc(fi);
        }
    }

    int p = 0, u = 1;
    q[0][0] = ri;
    q[0][1] = rj;
    t1[ri][rj] = 1;
    while(p != u){
        int i = q[p][0], j = q[p][1];
        p++;
        for(int k = 0; k < 4; k++){
            int ni = i + dir[k][0];
            int nj = j + dir[k][1];
            if(1 <= ni && ni <= n && 1 <= nj && nj <= m && v[ni][nj] != 'X' && t1[ni][nj] == 0){
                t1[ni][nj] = t1[i][j] + 1;
                q[u][0] = ni;
                q[u][1] = nj;
                u++;
            }
        }
    }

    p = 0, u = 1;
    q[0][0] = ji;
    q[0][1] = jj;
    t2[ji][jj] = 1;
    while(p != u){
        int i = q[p][0], j = q[p][1];
        p++;
        for(int k = 0; k < 4; k++){
            int ni = i + dir[k][0];
            int nj = j + dir[k][1];
            if(1 <= ni && ni <= n && 1 <= nj && nj <= m && v[ni][nj] != 'X' && !t2[ni][nj]){
                t2[ni][nj] = t2[i][j] + 1;
                q[u][0] = ni;
                q[u][1] = nj;
                u++;
            }
        }
    }

    int bi, bj;
    bi = bj = 0;
    t1[0][0] = 1000000000;
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++){
            if(t1[i][j] == t2[i][j] && t1[i][j] != 0 && t1[i][j] < t1[bi][bj]){
                bi = i;
                bj = j;
            }
        }
    fprintf(fo,"%d %d %d", t1[bi][bj] - 1, bj, bi);
    fclose(fi);
    fclose(fo);
    return 0;
}