Cod sursa(job #686897)

Utilizator samuelbumbarSamuel Bumbar samuelbumbar Data 21 februarie 2012 22:18:37
Problema Rj Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.95 kb
#include <fstream>
//#include <iomanip>

using namespace std;

ifstream fi ("rj.in");
ofstream fo ("rj.out");

string x[102];
int a[102][102], c[102][102], Tmin, i, j, n, m, v, p, u, jj, ii, y, b[102], Di[] = {0, -1, -1, 0, 1, 1, 1, 0, -1}, Dj[] = {0, 0, 1, 1, 1, 0, -1, -1, -1};

void citire () {
  fi >> n >> m;
  getline (fi, x[0]);
  for (i = 1; i <= n; i++) {
    getline (fi, x[i]);
    for (j = 0; j < m; j++)
      if (x[i][j] == 'X')
        a[i][j+1] = -1;
    else
      if (x[i][j] == ' ')
        a[i][j+1] = 0;
    else
      if (x[i][j] == 'R')
        a[i][j+1] = -2;
    else
      if (x[i][j] == 'J')
        a[i][j+1] = -3;
  }
  for (i = 0; i <= n+1; i++) {
    a[i][0] = -1; a[i][m+1] = -1;
  }
  for (j = 0; j <= m+1; j++) {
    a[0][j] = -1; a[n+1][j] = -1;
  }
}

void DrumRomeo () {
  c[i][j] = 1; p = 1; u = 1;
  b[1] = i * 1000 + j;
  while (p <= u) {
    i = b[p] / 1000; j = b[p] % 1000; p++;
    for (y = 1; y <= 8; y++) {
      ii = i + Di[y]; jj = j + Dj[y];
      if (c[ii][jj] == 0) {
        c[ii][jj] = c[i][j] + 1;
        b[++u] = ii * 1000 + jj;
      }
      else if (c[ii][jj] == -3) {
        c[ii][jj] = c[i][j] + 1;
        break;
      }
    }
  }
}

void DrumJulieta () {
  a[i][j] = 1; p = 1; u = 1;
  b[1] = i * 1000 + j;
  while (p <= u) {
    i = b[p] / 1000; j = b[p] % 1000; p++;
    for (y = 1; y <= 8; y++) {
      ii = i + Di[y]; jj = j + Dj[y];
      if (a[ii][jj] == 0) {
        a[ii][jj] = a[i][j] + 1;
        b[++u] = ii * 1000 + jj;
      }
      else if (a[ii][jj] == -2) {
        a[ii][jj] = a[i][j] + 1; //Tmin = (a[ii][jj]+1)/2;
        break;
      }
    }
  }
}

int main() {
  citire();
  for (i = 0; i <= n+1; i++) {
    for (j = 0; j <= m+1; j++)
      c[i][j] = a[i][j];
  }
  for (i = 1; i <= n; i++) {
    j = x[i].find("R");
    if (j != string::npos)
      break;
  }
  j++; DrumRomeo();
  for (i = 1; i <= n; i++) {
    j = x[i].find("J");
    if (j != string::npos)
      break;
  }
  j++; DrumJulieta();
//  if (Tmin % 2 == 0)
//    for (i = 1; i <= n; i++)
//      for (j = 1; j <= m; j++)
//        if (c[i][j] == Tmin and a[i][j] == Tmin-1) {
//          ii = i; jj = j; break;
//        }
//  else
//    for (i = 1; i <= n; i++)
//      for (j = 1; j <= m; j++)
//        if (a[i][j] == c[i][j] and a[i][j] == Tmin) {
//          ii = i; jj = j; break;
//        }
  Tmin = 1000000;
  for (i = 1; i <= n; i++)
    for (j = 1; j <= m; j++)
      if (c[i][j] != -1 && c[i][j] != 0 && c[i][j] == a[i][j] && c[i][j] < Tmin) {
        Tmin = c[i][j]; ii = i; jj = j;
      }
  fo << Tmin << ' ' << ii << ' ' << jj;
//  fo << '\n';
//  for (i = 1; i <= n; i++) {
//    for (j = 1; j <= m; j++)
//      fo << setw(2) << c[i][j] << ' ';
//      fo << '\n';
//}
//fo << '\n';
//  for (i = 1; i <= n; i++) {
//    for (j = 1; j <= m; j++)
//      fo << setw(2) << a[i][j] << ' ';
//      fo << '\n';
//}
    return 0;
}