Решение задачи Испытание замощением с Codeforces
Без пояснения   Просмотров: 83
Однажды Алиса делала уборку в своем подвале и заметила кое-что любопытное: бесконечное множество одинаковых деревянных фигур! Каждая фигура была сделана из пяти квадратных плиток, одна из была центральной, а остальные четыре примыкали к ней:
Около кусочков лежала большая квадратная доска. Доска разделена на n2 клеток, расположенных в n строках и n столбцах. Некоторые клетки уже заняты плитками, прибитыми к клеткам. Остальные клетки свободны.
Алиса подумала, сможет ли она заполнить доску полностью, используя найденные фигуры? Конечно, каждая фигура должна покрывать ровно пять ячеек доски, никакие две фигуры не должны перекрываться и ни одна фигура не должна вылезать за пределы доски. Однако доска была слишком большой, и Алиса не смогла покрыть ее вручную. Можете ли вы помочь ей определить, возможно ли полностью покрыть доску фигурами?
Около кусочков лежала большая квадратная доска. Доска разделена на n2 клеток, расположенных в n строках и n столбцах. Некоторые клетки уже заняты плитками, прибитыми к клеткам. Остальные клетки свободны.
Алиса подумала, сможет ли она заполнить доску полностью, используя найденные фигуры? Конечно, каждая фигура должна покрывать ровно пять ячеек доски, никакие две фигуры не должны перекрываться и ни одна фигура не должна вылезать за пределы доски. Однако доска была слишком большой, и Алиса не смогла покрыть ее вручную. Можете ли вы помочь ей определить, возможно ли полностью покрыть доску фигурами?