Решение задачи №154 от UniLecs (Тетрадь в клеточку - 2)

main.rs

const BLANK: u8 = 0;
const PAINTED: u8 = 1;

///Возвращает сторону самого большого квадрата, 
///который можно разместить в m, не накрывая закрашенных клеток,
///и количество таких квадратов.
fn count_max_squares<Row>(m: &[Row]) -> (usize, usize)
where
    Row: AsRef<[u8]>
{
    use std::cmp::Ordering;
    
    let side = m.len();
    assert!(side != 0);
    
    let mut max_sq = vec![vec![0; side]; side];
    let mut max_side = 0;
    let mut max_count = 0;
    
    //Заполняем первую строку
    for col in 0..side {
        if m[0].as_ref()[col] == BLANK {
            max_side = 1;
            max_count += 1;
            max_sq[0][col] = 1;
        } else {
            max_sq[0][col] = 0;
        }
    }
    
    //Заполняем первый столбец
    for row in 1..side {
        if m[row].as_ref()[0] == BLANK {
            max_side = 1;
            max_count += 1;
            max_sq[row][0] = 1;
        } else {
            max_sq[row][0] = 0;
        }
    }
    
    for row in 1..side {
        for col in 1..side {
            if m[row].as_ref()[col] == PAINTED {
                max_sq[row][col] = 0;
                continue
            }
            
            let left = max_sq[row][col - 1];
            let top = max_sq[row - 1][col];
            let corner = max_sq[row - 1][col - 1];
            
            let current = left.min(top).min(corner) + 1;
            
            match current.cmp(&max_side) {
                Ordering::Less => (),
                Ordering::Equal => {
                    max_count += 1;
                },
                Ordering::Greater => {
                    max_side = current;
                    max_count = 1;
                },
            }
            
            max_sq[row][col] = current;
        }
    }
    
    (max_side, max_count)
}

fn main() {
    use PAINTED as P;
    assert!(P != 0);
    
    let m = [
        [P, 0, 0, 0, 0, P],
        [0, P, 0, 0, 0, 0],
        [P, 0, 0, 0, 0, 0],
        [0, 0, P, 0, 0, 0],
        [0, 0, 0, 0, P, 0],
        [0, 0, P, 0, 0, 0],
    ];
    
    println!("{:?}", count_max_squares(&m)); //(3, 2)
    
    let m = [
        [0, 0, 0],
        [0, 0, P],
        [0, 0, 0]
    ];
    
    println!("{:?}", count_max_squares(&m)); //(2, 2)
}

Условие: https://tgraph.io/Anons-154-Tetrad-v-kletochku---2-02-01
Playground: https://play.rust-lang.org/?gist=f80b7a8e8f36d759af41ca452072ff43

Очевидно, в любой незакрашенной клетке можно разместить квадрат 1x1.

Пусть у нас в строке row и столбце col лежит правый нижний угол квадрата размеров k×k (row > 0, col > 0 при нумерации от нуля). Попробуем расширить квадрат вверх и влево до размеров k + 1×k + 1. Если это возможно (то есть никакие закрашенные клетки при этом не накрываются), полученный квадрат накрывает три квадрата размеров k×kс правыми нижними углами в клетках с координатами(row - 1, col), (row, col - 1)и(row - 1, col - 1)` (т. е. на одну клетку вверх, одну клетку вниз и одну клетку по диагонали вверх налево соответственно от правого нижнего угла увеличенного квадрата). В этом случае размер увеличенного квадрата на единицу больше, чем размеры накрытых квадратов.

Пусть теперь у нас есть таблица A, в каждой ячейке которой записана сторона максимального квадрата, правый нижний угол которого лежит в этой ячейке. Как нетрудно доказать от противного из рассуждений выше, для ячейки A[i, j] значение в этой ячейке равно min(A[i - 1, j], A[i, j - 1], A[i - 1, j - 1]) + 1 (при условии, что i, j > 0).

Для решения задачи мы строим вышеуказанную таблицу и попутно отслеживаем сторону максимального квадрата и их число. Для этого мы обходим таблицу по побочным диагоналям и назначаем ячейкам значениям, исходя из значений соседних ячеек. Для того, чтобы не проверять постоянно индексы на выход из диапазона, строку 0 и столбец 0 мы заполняем значением 1 для пустых ячеек и 0 для закрашенных.

Playground v2: https://play.rust-lang.org/?gist=14e84ca1c10fafb7262e672d1c23f429