Problem 871: Counting Cells in a Blob

blob pada grid Pada soal ini ditanyakan berapa ukuran dari blob yang terbesar dari sekumpulan blob yang diberikan. Bila diibaratkan papan catur, grid di sini adalah keseluruhan kotak berwarna putih sebagai dasar dan blob adalah sekumpulan kotak-kotak berwarna hitam. Secara mudah grid dapat disusun menggunakan array of string dengan penanda kotak hitam adalah karakter ‘1’. Menghitung ukuran terbesar blob dengan menyusuri kotak-kotak hitam ke arah kiri, kanan, atas, bawah dan diagonal secara rekursif, menghitung berapa banyaknya hingga terbentur dengan kotak putih.

Pada procedure CekGrid penyusuran itu terdiri tahapan seperti di bawah.

  1. Kiri horizontal
  2. Kanan horizontal
  3. Atas vertikal
  4. Bawah vertikal
  5. Kiri atas diagonal
  6. Kiri bawah diagonal
  7. Kanan atas diagonal
  8. Kanan bawah diagonal

http://icpcres.ecs.baylor.edu/onlinejudge/index.php?option=com_onlinejudge&Itemid=8&category=10&page=show_problem&problem=812

{$APPTYPE CONSOLE}
{$LONGSTRINGS OFF}
{$IFNDEF DELPHI}
  {$MODE Delphi}
  {$OPTIMIZATION ON}
{$ENDIF}

program blob_871;

var
  Kotak: array[1..25] of string[25];
  Lebar, Bar: Integer;

function CekGrid(X, Y: Integer): Integer;
begin
  Result := 1;
  Kotak[Y][X] := '0';
  // cek kiri hor --
  if (X > 1) and (Kotak[Y][X-1] = '1') then
    Inc(Result, CekGrid(X-1, Y));
  // cek kanan hor --
  if (X < Lebar) and (Kotak[Y][X+1] = '1') then
    Inc(Result, CekGrid(X+1, Y));
  // cek atas ver --
  if (Y > 1) and (Kotak[Y-1][X] = '1') then
    Inc(Result, CekGrid(X, Y-1));
  // cek bawah ver --
  if (Y < Bar) and (Kotak[Y+1][X] = '1') then
    Inc(Result, CekGrid(X, Y+1));
  // cek kiri atas diag --
  if (X > 1) and (Y > 1) and (Kotak[Y-1][X-1] = '1') then
    Inc(Result, CekGrid(X-1, Y-1));
  // cek kiri bawah diag --
  if (X > 1) and (Y < Bar) and (Kotak[Y+1][X-1] = '1') then
    Inc(Result, CekGrid(X-1, Y+1));
  // cek kanan atas diag --
  if (X < Lebar) and (Y > 1) and (Kotak[Y-1][X+1] = '1') then
    Inc(Result, CekGrid(X+1, Y-1));
  // cek kanan bawah diag --
  if (X < Lebar) and (Y < Bar) and (Kotak[Y+1][X+1] = '1') then
    Inc(Result, CekGrid(X+1, Y+1));
end;

var
  I, J, K, Max, Total: Integer;
{$IFDEF DELPHI}FT: Text;{$ENDIF}
begin
  {$IFDEF DELPHI}
  Assign(FT, 'grid.txt');
  Reset(FT);
  {$ENDIF}
  Readln({$IFDEF DELPHI}FT,{$ENDIF} Total);
  Readln({$IFDEF DELPHI}FT{$ENDIF});
  while Total > 0 do begin
    Bar := 0;
    repeat
      Inc(Bar);
      Readln({$IFDEF DELPHI}FT,{$ENDIF} Kotak[Bar]);
    until Kotak[Bar] = '';
    Dec(Bar);
    // periksa setiap grid --
    Lebar := Length(Kotak[1]);
    Max := 0;
    for I := 1 to Bar do begin
      for J := 1 to Lebar do
        if Kotak[I][J]='1' then begin
          K := CekGrid(J, I);
          if K > Max then Max := K;
        end;
    end;
    Writeln(Max);
    if Total > 1 then Writeln;
    Dec(Total);
  end;
  {$IFDEF DELPHI}Readln;{$ENDIF}
end.

1 Komentar »

  1. Daryl said

    saya tertarik dengan blob tapii saya belum tau ttg blob itu sendiri
    Apa Jika kita menggunakan BLOB ini bisa Dilakukan pencocokkan ??
    Tolong balas di email saya juga ya ,,,
    metropolis_star@yahoo.com

RSS feed for comments on this post · TrackBack URI

Tinggalkan Balasan

Isikan data di bawah atau klik salah satu ikon untuk log in:

Logo WordPress.com

You are commenting using your WordPress.com account. Logout / Ubah )

Gambar Twitter

You are commenting using your Twitter account. Logout / Ubah )

Foto Facebook

You are commenting using your Facebook account. Logout / Ubah )

Foto Google+

You are commenting using your Google+ account. Logout / Ubah )

Connecting to %s