File GridPaths.h

↰ Parent directory (ADS/optimization)

Two problems of dynamic programming on a matrix of m rows and n columns, each cell solved from its neighbours above and to the left:

Definition (ADS/optimization/GridPaths.h)

Detailed Description

  • largestSquare(): the largest square of nonzero cells of a 0/1 matrix. With S[ i ][ j ] the side of the largest one with its lower right corner in ( i , j ), S[ i ][ j ] = 0 on a zero cell and otherwise :math:` 1 + min( S[ i - 1 ][ j ] , S[ i - 1 ][ j - 1 ] , S[ i ][ j - 1 ] ) , since the three squares cover all the square of side one more but its corner; :math: Theta( m n ) ` time, :math:` Theta( n ) ` space keeping one row. The largest rectangle of ones takes :math:` Theta( m n ) ` too, by the largest rectangle in the histogram of each row.

  • countLatticePaths(): the monotone lattice paths from the upper left to the lower right cell, a step right or down, through the nonzero cells: :math:` N[ i ][ j ] = N[ i - 1 ][ j ] + N[ i ][ j - 1 ] ` on a free cell and 0 on a blocked one, :math:` Theta( m n ) ` time and :math:` Theta( n ) ` space. With no blocked cell they are :math:` binom{m + n - 2}{m - 1} ; with few blocked cells, the inclusion-exclusion on the blocked cells sorted takes :math: O( b^2 ) ` binomials for b of them.

The contracts [see File Contract.h]: the matrix is a rectangle; the square found is inside the matrix and all nonzero (checked at level 3). The functions are defined in GridPaths.tpp.

  1. Montresor, Algoritmi e Strutture Dati, 2025, chapter 13, https://algoritmicamente.it/materiali/libro/capitoli/cap13.pdf

    1. Skiena, M. A. Revilla, Programming Challenges, Springer, 2003, chapters 6 and 11

Donato Meoli

Dipartimento di Informatica Universita’ di Pisa

by Donato Meoli

Includes

Namespaces

Classes

Functions