Cod sursa(job #1514435)

Utilizator oanaroscaOana Rosca oanarosca Data 31 octombrie 2015 10:52:34
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.35 kb
#include <fstream>
#include <iomanip>

using namespace std;

struct pozitie {
  int lin; int col;
};

pozitie pct[3], ps, coada[100001], v, p;
int l, c, lin, col, i, mr[101][101], j, mj[101][101], prim, ultim;
int dl[] = {0, -1, -1, 0, 1, 1, 1, 0, -1}; //N, NE, E, SE, S, SV, V, NV
int dc[] = {0, 0, 1, 1, 1, 0, -1, -1, -1};
char ch;
int lib, ramase, minim = 2e9, lmin, cmin;

void bordare (int lin, int col) {
  int i;
  for (i = 0; i <= col; i++)
    mr[0][i] = mr[lin+1][i] = mj[0][i] = mj[lin+1][i] = -1;
  for (i = 0; i <= lin; i++)
    mr[i][0] = mr[i][col+1] = mj[i][0] = mj[i][col+1] = -1;
}

int main () {
  ifstream fi("rj.in");
  ofstream fo("rj.out");
  fi >> lin >> col; fi.get(ch);
  for (l = 1; l <= lin; l++) {
    for (c = 1; c <= col; c++) {
      fi.get(ch);
      if (ch == 'X')
        mr[l][c] = -1, mj[l][c] = -1;
      else {
        if (ch != ' ')
          pct[++i].lin = l, pct[i].col = c;
        lib++;
      }
    }
    fi.get();
  }
  bordare(lin, col);
  ps = pct[1]; ramase = lib;
  coada[1] = pct[1]; prim = ultim = 1; mr[ps.lin][ps.col] = 1;
  while (prim <= ultim and ramase) {
    p = coada[prim]; prim++;
    for (j = 1; j <= 8; j++) {
      v.lin = p.lin+dl[j]; v.col = p.col+dc[j];
      if (mr[v.lin][v.col] > mr[p.lin][p.col]+1 or not mr[v.lin][v.col]) {
        mr[v.lin][v.col] = mr[p.lin][p.col]+1, ramase--;
        ultim++, coada[ultim] = v;
      }
    }
  }
  ps = pct[2]; ramase = lib;
  coada[1] = pct[2]; prim = ultim = 1; mj[ps.lin][ps.col] = 1;
  while (prim <= ultim and ramase) {
    p = coada[prim]; prim++;
    for (j = 1; j <= 8; j++) {
      v.lin = p.lin+dl[j]; v.col = p.col+dc[j];
      if (mj[v.lin][v.col] > mj[p.lin][p.col]+1 or not mj[v.lin][v.col]) {
        mj[v.lin][v.col] = mj[p.lin][p.col]+1, ramase--;
        ultim++, coada[ultim] = v;
      }
    }
  }
  /*for (l = 1; l <= lin; l++) {
    for (c = 1; c <= col; c++)
      fo << setw(2) << mr[l][c] << ' ';
    fo << '\n';
  }
  fo << '\n';
  for (l = 1; l <= lin; l++) {
    for (c = 1; c <= col; c++)
      fo << setw(2) << mj[l][c] << ' ';
    fo << '\n';
  }*/
  for (l = 1; l <= lin; l++)
    for (c = 1; c <= col; c++)
      if (mj[l][c] > 0 and mr[l][c] == mj[l][c] and mj[l][c] < minim)
        minim = mr[l][c], lmin = l, cmin = c;
  fo << minim << ' ' << lmin << ' ' << cmin;
  return 0;
}