Prvi put kroz matricu

Osnovna ideja je da se formiraju svi podskupovi polja matrice između kojih postoji put (oni formiraju klase ekvivalencije tzv. komponente povezanosti). Svaki put kada se uspostavi veza između neka dva polja matrice, podskupovi kojima ona pripadaju se spajaju. Provera da li postoji put između dva polja matrice svodi se onda na proveru da li ona pripadaju istom podskupu.

Putanja od vrha do dna postoji ako i samo ako postoji putanja od bilo kog polja u prvoj vrsti matrice do bilo kog polja u poslednjoj vrsti matrice. To bi dovelo do toga da u svakom koraku moramo da proveravamo sve parove elemenata iz prve i poslednje vrste. Međutim, možemo i bolje. Dodaćemo veštački početni čvor (nazovimo ga izvor) i spojićemo ga sa svim čvorovima u prvoj vrsti matrice i završni čvor (nazovimo ga ušće) koji ćemo spojiti sa svim čvorovima u poslednjoj vrsti matrice. Tada se u svakom koraku može proveriti samo da li su izvor i ušće spojeni tj. da li pripadaju istom podskupu.

Slika 1: Komponente povezanosti su obojene različitim bojama. Pošto su izvor i ušće isto obojeni, postoji put od vrha do dna.

Podskupove možemo čuvati pomoću strukture podataka za predstavljanje disjunktnih podskupova.

// jednostavnosti radi matricu čuvamo u nizu dimenzije n*n
// redni broj elementa (x, y) u matrici
int kod(int x, int y, int n) {
  return x*n + y;
}

int main() {
  // dimenzija matrice
  int n;
  cin >> n;
  
  // alociramo matricu n*n tj. niz u kom čuvamo njene elemente
  vector<vector<bool>> a(n);
  for (int i = 0; i < n; i++)
    a[i].resize(n, false);

  // dva dodatna veštačka čvora
  const int izvor = n*n;
  const int usce = n*n+1;

  // inicijalizujemo union-find strukturu za sve elemente matrice 
  // (njih n*n), izvor i ušće
  UF_inicijalizacija(n*n + 2);

  // spajamo izvor sa svim elementima u prvoj vrsti matrice
  for (int i = 0; i < n; i++)
    UF_unija(izvor, kod(0, i, n));

  // spajamo sve elemente u poslednjoj vrsti matrice sa ušćem
  for (int i = 0; i < n; i++)
    UF_unija(kod(n-1, i, n), usce);

  // broj jedinica
  int m;
  cin >> m;

  // korak u kom se spajaju izvor i usce
  int korak = -1;

  // ucitavamo i obrađujemo jednu po jednu jedinicu
  for (int k = 1; k <= m; k++) {
    int x, y;
    cin >> x >> y;
    // ako je u matrici već jedinica, nema šta da se radi
    if (a[x][y]) continue;
    // upisujemo jedinicu u matricu
    a[x][y] = true;
    // povezujemo podskupove u sva četiri smera
    if (x > 0 && a[x-1][y])
      UF_unija(kod(x, y, n), kod(x-1, y, n));
    if (x + 1 < n && a[x+1][y])
      UF_unija(kod(x, y, n), kod(x+1, y, n));
    if (y > 0 && a[x][y-1])
      UF_unija(kod(x, y, n), kod(x, y-1, n));
    if (y + 1 < n && a[x][y+1])
      UF_unija(kod(x, y, n), kod(x, y+1, n));
    // proveravamo da li su izvor i ušće spojeni
    if (UF_pronadji(izvor) == UF_pronadji(usce)) {
      korak = k;
      break;
    }
  }

  cout << korak << endl;

  return 0;
}

#include <iostream>
#include <vector>

using namespace std;

vector<int> UF_roditelj;
vector<int> UF_rang;

void UF_inicijalizacija(int n) {
  UF_roditelj.resize(n);
  UF_rang.resize(n);
  for (int i = 0; i < n; i++) {
    UF_roditelj[i] = i;
    UF_rang[i] = 0;
  }
}

int UF_pronadji(int x) {
  while (x != UF_roditelj[x]) {
    UF_roditelj[x] = UF_roditelj[UF_roditelj[x]];
    x = UF_roditelj[x];
  }
  return x;
}

void UF_unija(int x, int y) {
  int fx = UF_pronadji(x), fy = UF_pronadji(y);
  if (UF_rang[fx] < UF_rang[fy])
    UF_roditelj[fx] = fy;
  else if (UF_rang[fy] < UF_rang[fx])
    UF_roditelj[fy] = fx;
  else {
    UF_roditelj[fx] = fy;
    UF_rang[fy]++;
  }
}

// jednostavnosti radi matricu čuvamo u nizu dimenzije n*n
// redni broj elementa (x, y) u matrici
int kod(int x, int y, int n) {
  return x*n + y;
}

int main() {
  // dimenzija matrice
  int n;
  cin >> n;
  
  // alociramo matricu n*n tj. niz u kom čuvamo njene elemente
  vector<vector<bool>> a(n);
  for (int i = 0; i < n; i++)
    a[i].resize(n, false);

  // dva dodatna veštačka čvora
  const int izvor = n*n;
  const int usce = n*n+1;

  // inicijalizujemo union-find strukturu za sve elemente matrice 
  // (njih n*n), izvor i ušće
  UF_inicijalizacija(n*n + 2);

  // spajamo izvor sa svim elementima u prvoj vrsti matrice
  for (int i = 0; i < n; i++)
    UF_unija(izvor, kod(0, i, n));

  // spajamo sve elemente u poslednjoj vrsti matrice sa ušćem
  for (int i = 0; i < n; i++)
    UF_unija(kod(n-1, i, n), usce);

  // broj jedinica
  int m;
  cin >> m;

  // korak u kom se spajaju izvor i usce
  int korak = -1;

  // ucitavamo i obrađujemo jednu po jednu jedinicu
  for (int k = 1; k <= m; k++) {
    int x, y;
    cin >> x >> y;
    // ako je u matrici već jedinica, nema šta da se radi
    if (a[x][y]) continue;
    // upisujemo jedinicu u matricu
    a[x][y] = true;
    // povezujemo podskupove u sva četiri smera
    if (x > 0 && a[x-1][y])
      UF_unija(kod(x, y, n), kod(x-1, y, n));
    if (x + 1 < n && a[x+1][y])
      UF_unija(kod(x, y, n), kod(x+1, y, n));
    if (y > 0 && a[x][y-1])
      UF_unija(kod(x, y, n), kod(x, y-1, n));
    if (y + 1 < n && a[x][y+1])
      UF_unija(kod(x, y, n), kod(x, y+1, n));
    // proveravamo da li su izvor i ušće spojeni
    if (UF_pronadji(izvor) == UF_pronadji(usce)) {
      korak = k;
      break;
    }
  }

  cout << korak << endl;

  return 0;
}

Prvi put kroz matricu - Rešenje