DOMENII  (Timisoara - pregatire, ian. 1996)

	Se considera un teren de forma dreptunghiulara de dimensiune m*n, 
impartit in parcele cu latura de o unitate. Terenul este impartit la p 
persoane, fiecare parcela fiind marcata cu numarul persoanei careia ii 
apartine. Mai multe parcele invecinate (vecinatatea se considera in 
directiile N, S, E, V) care apartin aceleasi persoane formeaza un domeniu; 
o persoana poate detine mai multe domenii.
	Intre cele p persoane pot exista doua tipuri de relatii:
 - relatia parinte - fiu, notata cu 1, care este unidirectionala: relatia
           1 i j indica faptul ca i este parinte a lui j;
 - relatia sot - sotie, notata cu 2, care este bidirectionala: relatia 
           2 i j indica faptul ca i si j sunt casatoriti.
	O familie este formata dintr-o persoana sau din parinti si copiii 
lor care nu sint casatoriti (se considera ca o persoana casatorita isi 
intemeiaza propria familie).
	Se cere:
 a) sa se determine domeniul maxim pentru fiecare persoana;
 b) sa se determine si sa se afiseze familiile, iar apoi sa se determine
    domeniul maxim pentru fiecare familie.
	Fisierul de intrare ziua7_2.inp poate contine mai multe seturi de 
date delimitate de cate un rand liber; fiecare set de date contine:
     - pe prima linie numerele m, n si p care reprezinta dimensiunile terenului,
       respectiv numarul de persoane;
     - pe urmatoarele m linii matricea de numere intregi care reprezinta terenul
       in care fiecare parcela este numerotata cu indicele proprietarului;
     - pe urmatoarele linii se dau relatiile existente intre persoane, sub
       forma: 1 i j sau 2 i j.
Corespunzator unui set de date de intrare, fisierul ziua7_2.out contine:
     - matricea care reprezinta terenul, dar pentru fiecare persoana este 
       marcat doar domeniul maxim, in rest afisindu-se spatii;
     - in continuare se afiseaza familiile: membrii fiecarei familii pe cate 
       o linie; 
     - matricea care reprezinta terenul indicandu-se pentru fiecare familie 
       domeniul ei maxim, restul completindu-se cu spatiu.
Exemplu: pentru setul de date de intrare:
5 5 5
1 2 3 1 5
3 3 3 3 5
2 1 3 1 5
2 1 1 1 5
2 2 2 4 4
1 1 2
1 1 3
2 3 4
iesirea este:
    3   5
3 3 3 3 5
2 1 3 1 5
2 1 1 1 5
2 2 2
familia 1: 1 2
familia 2: 3 4
familia 3: 5
    2   3
2 2 2 2 3
1 1 2 1 3
1 1 1 1 3
1 1 1
-------------------------------------------------------
Rezolvare: (Mihai Stroe)

  Am considerat ca o persoana are cel mult un parinte(altfel,ar avea
     doi parinti casatoriti,situatie care nu aduce informatii noi,sau ar
     apartine mai multor familii) si e casatorita cu cel mult o persoana.
       Pentru fiecare persoana se pastreaza informatii care desemneaza
     parintele si sotul ( sotia ).Daca o persoana este casatorita,campul
     care pastreaza tatal devine 0.
       Ariile se calculeaza cu ajutorul unei functii recursive.
       Pentru determinarea familiilor se foloseste algoritmul Roy-Warshal
     ( se poate folosi orice alt algoritm pentru determinarea componentelor
     conexe din graful dat de relatiile de rudenie ).Matricea rezultata
     se prelucreaza pe linii.
       Se foloseste aceeasi functie recursiva pentru determinarea ariilor
     maxime ocupate de fiecare familie.

var a,b,mat:array[0..100,0..100]of byte;
    sot,tata:array[1..100]of byte;
    arie:array[1..100,1..3]of integer;
    nrfam,i,j,k,l,m,n,p:integer;
    fi,fo:text;
    fam:array[1..100]of set of byte;

function supr(i,j,k:byte):integer;
begin
  supr:=0;
  if k=0 then exit;
  if b[i,j]<>k then exit;
  b[i,j]:=0;
  supr:=1+supr(i-1,j,k)+supr(i+1,j,k)+supr(i,j+1,k)+supr(i,j-1,k);
end;

procedure fill(i,j,k:byte);
begin
  if mat[i,j]<>k then exit;
  if b[i,j]<>0 then exit;
  b[i,j]:=k;
  fill(i+1,j,k);
  fill(i,j+1,k);
  fill(i-1,j,k);
  fill(i,j-1,k);
end;

procedure solve;
begin
  for i:=1 to p do
      if sot[i]<>0 then tata[i]:=0;
  for i:=1 to p do
      begin
        a[i,tata[i]]:=1;
        a[tata[i],i]:=1;
        a[i,sot[i]]:=1;
        a[sot[i],i]:=1;
      end;
  b:=mat;
  for i:=1 to m do
      for j:=1 to n do
          begin
            l:=supr(i,j,b[i,j]);
            if l>arie[mat[i,j],3] then
             begin
               arie[mat[i,j],1]:=i;
               arie[mat[i,j],2]:=j;
               arie[mat[i,j],3]:=l;
             end;
          end;
  for i:=1 to p do
      fill(arie[i,1],arie[i,2],i);
  for i:=1 to m do
      begin
        for j:=1 to n do
            if b[i,j]=0 then write(fo,'  ')
                        else write(fo,b[i,j],' ');
        writeln(fo);
      end;
  for i:=1 to p do a[i,i]:=1;
  for k:=1 to p do
      for i:=1 to p do
          for j:=1 to p do
              if a[i,k]+a[k,j]=2 then begin a[i,j]:=1;a[j,i]:=1;end;
  nrfam:=0;
  for i:=1 to p do
      if a[i,i]=1 then
         begin
           inc(nrfam);
           for j:=1 to p do
               if a[i,j]=1 then
                  begin
                    fam[nrfam]:=fam[nrfam]+[j];
                    if i<>j then
                    for k:=1 to p do
                        a[j,k]:=0;
                  end;
         end;
  for i:=1 to nrfam do
      begin
        write(fo,'Familia ',i,': ');
        for j:=1 to p do
            if j in fam[i] then write(fo,j,' ');
        writeln(fo);
      end;
  b:=mat;
  for i:=1 to nrfam do
      for j:=1 to m do
          for k:=1 to n do
              if b[j,k]in fam[i] then b[j,k]:=i;
  mat:=b;
  fillchar(arie,sizeof(arie),0);
    for i:=1 to m do
      for j:=1 to n do
          begin
            l:=supr(i,j,b[i,j]);
            if l>arie[mat[i,j],3] then
             begin
               arie[mat[i,j],1]:=i;
               arie[mat[i,j],2]:=j;
               arie[mat[i,j],3]:=l;
             end;
          end;
  for i:=1 to p do
      fill(arie[i,1],arie[i,2],i);
  for i:=1 to m do
      begin
        for j:=1 to n do
            if b[i,j]=0 then write(fo,'  ')
                        else write(fo,b[i,j],' ');
        writeln(fo);
      end;
  writeln(fo,'****************');
end;

procedure readdata;
begin
  assign(fi,'ziua7_2.inp');
  reset(fi);
  assign(fo,'ziua7_2.out');
  rewrite(fo);
  while not eof(fi)do
    begin
      fillchar(mat,sizeof(mat),0);
      fillchar(b,sizeof(b),0);
      fillchar(a,sizeof(a),0);
      fillchar(sot,sizeof(sot),0);
      fillchar(tata,sizeof(tata),0);
      fillchar(arie,sizeof(arie),0);
      nrfam:=0;
      fillchar(fam,sizeof(fam),0);
      readln(fi,m,n,p);
      for i:=1 to m do
          begin
            for j:=1 to n do
              read(fi,mat[i,j]);
            readln(fi);
          end;
      while not seekeoln(fi)do
        begin
          readln(fi,k,i,j);
          if k=1 then tata[j]:=i
                 else begin sot[i]:=j;sot[j]:=i;end;
        end;
      readln(fi);
      solve;
    end;
  close(fi);
  close(fo);
end;

begin
  {$m 65000,0,0}
  readdata;
end.
