Cod sursa(job #2054807)

Utilizator andrei_diaconu11Andrei C. Diaconu andrei_diaconu11 Data 2 noiembrie 2017 16:13:06
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.84 kb
#include <stdio.h>
#include <queue>
using namespace std;

bool viz[102][102][2];
int dist[102][102][2];

struct coord{
  int x, y;
  coord operator +(coord a){
    return {x + a.x, y + a.y};
  }
} dir[] = { {-1,0}, {-1,1}, {0,1}, {1,1}, {1,0}, {1,-1}, {0,-1}, {-1,-1} };

queue <coord> q;

void lee(coord start, int p){
  coord aux, poz;
  q.push(start);
  viz[start.x][start.y][p] = true;
  dist[start.x][start.y][p] = 1;
  while(q.size() > 0){
    poz = q.front();
    q.pop();
    for(int d = 0; d < 8; d++){
      aux = poz + dir[d];
      if(viz[aux.x][aux.y][p] == false){
        viz[aux.x][aux.y][p] = true;
        q.push(aux);
        dist[aux.x][aux.y][p] = dist[poz.x][poz.y][p] + 1;
      }
    }
  }
}

int main()
{
  int n, m, i, j, tmin, minx, miny;
  FILE *fi =  fopen("rj.in", "r"), *fo = fopen("rj.out", "w");
  fscanf(fi, "%d%d", &n, &m);
  fgetc(fi);
  coord R, J;
  char ch;
  for(i = 1; i <= n; i++){
    bool stop = false;
    for(j = 1; j <= m; j++){
      if(!stop)
        ch = fgetc(fi);
      if(ch == '\n')
        stop = true;
      if(ch == 'R')
        R = (coord){i, j};
      else if(ch == 'J')
        J = (coord){i, j};
      else if(ch == 'X')
        viz[i][j][0] = viz[i][j][1] = true;
    }
    if(!stop)
      fgetc(fi);
  }
  for(i = 0; i <= n; i++)
    viz[i][0][0] = viz[i][0][1] = viz[i][m + 1][0] = viz[i][m + 1][1] = true;
  for(j = 0; j <= m; j++)
    viz[0][j][0] = viz[0][j][1] = viz[n + 1][j][0] = viz[n + 1][j][1] = true;
  viz[n + 1][m + 1][0] = viz[n + 1][m + 1][1] = true;
  lee(R,0);
  lee(J,1);
  tmin = 2000000000;
  for(i = 1; i <= n; i++)
    for(j = 1; j <= m; j++){
      if(dist[i][j][0] == dist[i][j][1] && dist[i][j][0] != 0 && tmin > dist[i][j][0]){
        tmin = dist[i][j][0];
        minx = i;
        miny = j;
      }
    }
  fprintf(fo, "%d %d %d", tmin, minx, miny);
  fclose(fi);
  fclose(fo);
  return 0;
}