Flood Fill Algoritması

Flood Fill , Hackerrank’te bir soruyu cozerken ogrendigim ve hosuma giden bir algoritma. Burada da kisaca deginmek istedim.

Flood Fill algoritmasi, paintteki doldurma kabinin (isminin bu olduguna emin degilim ama anladiniz diye varsayiyorum) islevini gorur. Biliyorsunuz bu alet birbirine bitisik ve ayni renkte olan pikselleri icindeki boyanin rengine boyamaktaydi. Komsuluk iliskisinde yer almayan pikseller ise boyanmamaktaydi. Iste Flood Fill algoritmasi aynen bunu yapar. Parametre olarak aldigi bir baslangic pikselinden baslayarak sagi,solu,ustu ve altinda kalan komsu piksellerini (ayrica opsiyonel olarak caprazlarini da katabiliriz) adim adim boyar. Boyama islemi sirasinda o anda uzerinde operasyon yapilan pikselin boyasi kontrol edilir, eger zaten boyandiysa o piksel atlanir.

Hackerrank’teki sorunun linkini verelim;

https://www.hackerrank.com/challenges/connected-cell-in-a-grid/problem

Go dilinde yazilmis kodu asagiya yapistiriyorum;

package main

import (
    "bufio"
    "fmt"
    "io"
    "os"
    "strconv"
    "strings"
)

var matrixGlob [][]int32
var colorValueMap = make(map[int]int)

func floodFill(rowIndex,columnIndex,color int) {
    
    if rowIndex>=len(matrixGlob) || rowIndex<0 || columnIndex >= len(matrixGlob[0]) || columnIndex<0 || matrixGlob[rowIndex][columnIndex] == int32(color) {
        return
    }
    if matrixGlob[rowIndex][columnIndex] != 1 {
        return
    }

    matrixGlob[rowIndex][columnIndex] = int32(color)
    colorValueMap[color] +=1
    floodFill(rowIndex+1,columnIndex,color)
    floodFill(rowIndex+1,columnIndex+1,color)
    floodFill(rowIndex+1,columnIndex-1,color)
    floodFill(rowIndex-1,columnIndex,color)
    floodFill(rowIndex-1,columnIndex+1,color)
    floodFill(rowIndex-1,columnIndex-1,color)
    floodFill(rowIndex,columnIndex+1,color)
    floodFill(rowIndex,columnIndex-1,color)
    return
}

// Complete the connectedCell function below.
func connectedCell(matrix [][]int32) int32 {
    matrixGlob = matrix
    currentColor := 2
    for row:=0 ; row<len(matrix) ; row++ {
        for column:=0 ; column<len(matrix[0]) ; column++ {
            floodFill(row,column,currentColor)
            currentColor += 1 
        }
    }

    maxArea := 0
    for _ , value := range colorValueMap {
        if value>maxArea {
            maxArea = value
        }
    }
    return int32(maxArea)
}

func main() {
    reader := bufio.NewReaderSize(os.Stdin, 1024 * 1024)

    stdout, err := os.Create(os.Getenv("OUTPUT_PATH"))
    checkError(err)

    defer stdout.Close()

    writer := bufio.NewWriterSize(stdout, 1024 * 1024)

    nTemp, err := strconv.ParseInt(readLine(reader), 10, 64)
    checkError(err)
    n := int32(nTemp)

    mTemp, err := strconv.ParseInt(readLine(reader), 10, 64)
    checkError(err)
    m := int32(mTemp)

    var matrix [][]int32
    for i := 0; i < int(n); i++ {
        matrixRowTemp := strings.Split(readLine(reader), " ")

        var matrixRow []int32
        for _, matrixRowItem := range matrixRowTemp {
            matrixItemTemp, err := strconv.ParseInt(matrixRowItem, 10, 64)
            checkError(err)
            matrixItem := int32(matrixItemTemp)
            matrixRow = append(matrixRow, matrixItem)
        }

        if len(matrixRow) != int(int(m)) {
            panic("Bad input")
        }

        matrix = append(matrix, matrixRow)
    }

    result := connectedCell(matrix)

    fmt.Fprintf(writer, "%d\n", result)

    writer.Flush()
}

func readLine(reader *bufio.Reader) string {
    str, _, err := reader.ReadLine()
    if err == io.EOF {
        return ""
    }

    return strings.TrimRight(string(str), "\r\n")
}

func checkError(err error) {
    if err != nil {
        panic(err)
    }
}

Kaynaklar

1. https://www.geeksforgeeks.org/flood-fill-algorithm-implement-fill-paint/
2. https://guide.freecodecamp.org/algorithms/flood-fill/
3. http://bilgisayarkavramlari.sadievrenseker.com/2008/10/21/tasirma-algoritmasi-flood-filling-algorithm/