Обозначим каждый узел клетчатой доски целыми значениями, где i - номер строки, j - номер столбца. Узел с наименьшими i и j будет нижним левым углом таблицы, а узел с наибольшими i и j будет верхним правым углом таблицы. Из условия задачи следует, что все клетки и все незанятые внутренние узлы таблицы должны быть побиты. При этом необходимо расставить как можно меньше сторожевых башен. Понятно, что одна башня может покрывать не более четырех клеток (две диагональные и две по горизонтали/вертикали). Для выполнения условий задачи будем расставлять сторожевые башни во внутренние узлы таблицы следующим образом: 1. Нижний левый угол (узел с наибольшими значениями i и j) будет покрыт одной башней. 2. Каждый узел на границе таблицы, кроме нижнего левого угла, будет покрыт одной башней. 3. Оставшиеся внутренние узлы, т.е. все узлы, у которых i и j не принимают минимальных и максимальных значений, будут покрыты двумя башнями. При этом первая башня будет покрывать узлы с четными i и j, а вторая - с нечетными i и j. Пример расстановки сторожевых башен в таблице 6x6: 1 1 2 2 3 3 1 1 2 2 3 3 4 4 5 5 6 6 4 4 5 5 6 6 7 7 8 8 9 9 7 7 8 8 9 9 Каждое число обозначает номер башни, которая покрывает соответствующий узел. Башня с номером 1 покрывает узлы с четными i и j, башня с номером 2 покрывает узлы с нечетными i и j. Таким образом, все клетки и все незанятые внутренние узлы покрыты башнями. Всего использовано 9 башен. Проверим выполнение условий задачи: 1. Все клетки. Все клетки покрыты башнями, поэтому все они побиты. 2. Все незанятые внутренние узлы. Все узлы, кроме узлов на границе, покрыты башнями. При этом мы использовали наименьшее возможное количество башен (только 2 для всех внутренних узлов), поэтому все незанятые внутренние узлы тоже покрыты. 3. Узлы на границе. В условии задачи сказано, что узлы на границе покрывать башнями не требуется, поэтому они могут оставаться непокрытыми. Таким образом, решение задачи состоит в том, чтобы использовать одну башню для нижнего левого угла таблицы и узлов на границе, и две башни для оставшихся внутренних узлов, причем первая башня покрывает узлы с четными i и j, а вторая - с нечетными i и j. Всего используется 9 башен.