Grade 12 · 6 algorithmsCitește în română

Grid algorithms: Lee and flood fillAlgoritmi pe grile: Lee și fill

Every grid algorithms: lee and flood fill algorithm from the Romanian high school curriculum, with the idea explained, its complexity, examples and code you can edit and run right here.

Create a free account Browse the collection

6algorithms
6chapters
1grade

Grid algorithms: Lee and flood fill

Algoritmi pe grile: Lee și fill · 6 algorithms

Flood fill: the largest regionFill — cea mai mare zonăThe same matrix of 0s and 1s, but now we want the number of cells of the largest region of 1s (adjacency through sides). This time the fill is done…O(n²)
Flood fill: the number of regionsFill — numărul de zoneThe matrix has n rows and m columns, with 1 for land and 0 for water. A region is a maximal group of 1 cells connected through their sides (up,…O(n²)
Islands in 8 directionsInsule în 8 direcțiiLike counting regions, but two land cells (1) belong to the same island if they touch even at a corner, i.e. the neighbourhood has 8 directions. The…O(n²)
Lee with multiple sourcesLee cu mai multe surseThe grid holds 0 (free), 1 (wall) and 2 (source, for example a well). For every free cell we want the minimum number of steps to the nearest source.…O(n²)
Lee: the shortest path in a gridLee — drumul minim într-o grilăThe grid has n rows and m columns: 0 = free, 1 = obstacle. We can move up, down, left, right. Lee's algorithm is a breadth-first search: d[xs][ys] =…O(n²)
Lee with path reconstructionLee cu reconstituirea drumuluiAfter Lee has filled the distance matrix, the path is rebuilt from the end towards the start: if we are in a cell with value k, one of its…O(n²)