Floodfill

Floodfill adalah algoritma untuk mencari luas suatu pulau. Penjelasan lengkapnya dapat dilihat di Wikipedia.

Idenya adalah, kita mencari objek pulau ke 4 arah secara rekursif secara berulang-ulang. Algoritmanya :

  1. fungsi floodfill(x,y) //asumsikan diset array pulau[][]
  2. pulau[x,y] = laut //pulau yang telah dikunjungi ubah jadi laut
  3. luas++ //luas pulau bertambah
  4. if (pulau[x-1,y]=pulau) floodfill(x-1,y)
  5. //begitu pula untuk 3 arah lainnya
  6. selesai

Berikut kode versi saya, asumsikan bahwa 0 adalah daratan dan 1 adalah lautan :

#include <algorithm>
#include <cstdio>
using namespace std;
char pulau[1000][1000];
int luas=0;
void floodfill(int y,int x) {
     luas++;
     pulau[y][x]='1';
     if (pulau[y][x-1]=='0') {
        floodfill(y,x-1);
        }
     if (pulau[y][x+1]=='0') {
        floodfill(y,x+1);
        }
     if (pulau[y-1][x]=='0') {
        floodfill(y-1,x);
        }
     if (pulau[y+1][x]=='0') {
        floodfill(y+1,x);
        }
     }
int main() {
    int r,c;
    scanf("%d %d",&r,&c);
    for (int i=0;i<r;i++) scanf("%s",&pulau[i]);
    int x,y;
    for (int i=0;i<r;i++) {
        for (int j=0;j<c;j++) {
            if (pulau[i][j]=='K') {
               x=j;
               y=i;
               break;
               }
            }
        }
    floodfill(y,x);
    printf("%d\n",luas);
    }

Leave a Reply

Please log in using one of these methods to post your comment:

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