Problem 871: Counting Cells in a Blob

March 15, 2009 at 2:18 am | Posted in ACM Contest | 1 Comment
Tags: ,

Oleh: Mpu Gondrong

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 Comment »

RSS feed for comments on this post. TrackBack URI

  1. nice posting brother


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Create a free website or blog at WordPress.com.
Entries and comments feeds.

%d bloggers like this: