Cod sursa(job #1295166)

Utilizator hrazvanHarsan Razvan hrazvan Data 18 decembrie 2014 21:44:27
Problema Rj Scor 0
Compilator c Status done
Runda Arhiva de probleme Marime 1.7 kb
#include <stdio.h>
#define MAXN 100
#define INF 2000000000
char s[MAXN + 1], ma[MAXN][MAXN];
int ro[MAXN][MAXN], ju[MAXN][MAXN];
int d[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};

void bfs(int dist[MAXN][MAXN], int l, int c, int n, int m){
  int k, nl, nc, lin[MAXN * MAXN], col[MAXN * MAXN], st = 0, dr = 1;
  lin[0] = l;
  col[0] = c;
  dist[l][c] = 1;
  while(st < dr){
    for(k = 0; k < 4; k++){
      nl = lin[st] + d[k][0];
      nc = col[st] + d[k][1];
      if(nl >= 0 && nl < n && nc >= 0 && nc < m){
        if(ma[nl][nc] == 0 && dist[nl][nc] == 0){
          dist[nl][nc] = dist[lin[st]][col[st]] + 1;
          lin[dr] = nl;
          col[dr] = nc;
          dr++;
        }
      }
    }
    st++;
  }
}

int main(){
  FILE *in = fopen("rj.in", "r");
  int n, m, i, j, l1, c1, l2, c2;
  fscanf(in, "%d%d", &n, &m);
  fgetc(in);
  for(i = 0; i < n; i++){
    fgets(s, MAXN + 1, in);
    for(j = 0; j < m; j++){
      switch(s[j]){
        case ' ':
          ma[i][j] = 0;
          break;
        case 'X':
          ma[i][j] = 1;
          break;
        case 'R':
          l1 = i;
          c1 = j;
          ma[i][j] = 0;
          break;
        case 'J':
          l2 = i;
          c2 = j;
          break;
      }
    }
  }
  bfs(ro, l1, c1, n, m);
  bfs(ju, l2, c2, n, m);
  int min = INF, l, c;
  for(i = 0; i < n; i++){
    for(j = 0; j < m; j++){
      if(ro[i][j] == ju[i][j] && ma[i][j] == 0 && ro[i][j] != 0)
        if(min > ro[i][j]){
          min = ro[i][j];
          l = i;
          c = j;
        }
    }
  }
  FILE *out = fopen("rj.out", "w");
  fprintf(out, "%d %d %d", min - 1, l + 1, c + 1);
  fclose(out);
  return 0;
}