Cod sursa(job #1992457)

Utilizator PopoviciRobertPopovici Robert PopoviciRobert Data 20 iunie 2017 15:05:36
Problema Rj Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.79 kb
#include <bits/stdc++.h>
#define MAXN 100
#define l first
#define c second

char mat[MAXN + 2][MAXN + 2];
int dist[2][MAXN + 2][MAXN + 2];

char dl[] = {-1, -1, -1, 0, 0, 1, 1, 1}, dc[] = {-1, 0, 1, -1, 1, -1, 0, 1};

std::pair <int, int> q[MAXN * MAXN + 1];

int n, m;

inline bool check(int l, int c) {
    if(l == 0 || l == n + 1 || c == 0 || c == m + 1)
       return 0;
    return 1;
}

inline void bfs(int l, int c, int t) {
    int b = 0, e = 1;
    q[0] = {l, c};
    dist[t][l][c] = 1;
    do{
       for(int i = 0; i < 8; i++)
         if(check(q[b].l + dl[i], q[b].c + dc[i]) && mat[q[b].l + dl[i]][q[b].c + dc[i]] != 'X' && dist[t][q[b].l + dl[i]][q[b].c + dc[i]] == 0) {
            q[e].l = q[b].l + dl[i];
            q[e].c = q[b].c + dc[i];
            dist[t][q[e].l][q[e].c] = dist[t][q[b].l][q[b].c] + 1;
            e++;
         }
       b++;
    }while(b < e);
}

int main() {
    FILE *fi, *fout;
    int i, j, lr, cr, lj, cj;
    fi=fopen("rj.in" ,"r");
    fout=fopen("rj.out" ,"w");
    fscanf(fi,"%d%d" ,&n,&m);
    for(i = 1; i <= n; i++) {
      for(j = 1; j <= m; j++) {
         fscanf(fi,"%c" ,&mat[i][j]);
         if(mat[i][j] == 'R') {
            lr = i;
            cr = j;
         }
         if(mat[i][j] == 'J') {
            lj = i;
            cj = j;
         }
      }
      fgetc(fi);
    }
    bfs(lr, cr, 1);
    bfs(lj, cj, 0);
    int min = n * m + 1;
    for(i = 1; i <= n; i++)
      for(j = 1; j <= m; j++)
        if(dist[0][i][j] == dist[1][i][j] && dist[0][i][j] > 0)
           min = std::min(min, dist[0][i][j]);
    for(i = 1; i <= n; i++)
      for(j = 1; j <= m; j++)
        if(dist[0][i][j] == min && dist[0][i][j] == dist[1][i][j]) {
           fprintf(fout,"%d %d %d" ,i, j, min - 1);
           return 0;
        }
    fclose(fi);
    fclose(fout);
    return 0;
}