Алгоритмы, дискретная математика и пр.'s Journal (original) (raw)

12:47p

Задача о раскраске плоскости переформулировал !

Пусть дан квадрат на плоскости, разбитый равномерной 2-мерной сеткой на N ячеек.
Под окраской квадрата будем понимать окраску его ячеек в 2 цвета (белый или черный).
Для каждой окраски посчитаем число =Сумма F(i), где Cумма берется по всем N ячейкам,
а F(i) считается следующим образом:

F(i)=(Общее Число соседей i-ой ячейки)-(Число соседей i-ой ячейки,имеющие тот же цвет, что и i-ая яейка)),возведенное в квадрат. Под соседями ячейки понимается яейки имеющие с ней общую грань, т е каждая ячейка имеет от 2-х до 4-х соседей, в зависимости от ее расположения на квадрате.

ЗАДАЧА

Пусть дан квадрат на плоскости, разбитый равномерной 2-мерной сеткой на N ячеек.
Пусть вначале только некоторое количество ячеек раскрашено в белый или черный цвет.

Нужно окрасить оставшиеся клетки таким образом, чтобы определенное выше число принимало минимальное значение