На рисунке изображена клетчатая доска. Будем считать, что фишка на этой доске видит другую фишку, если они расположены либо в одной вертикали, либо в одной горизонтали, причём между ними нет границ доски. Сколькими способами можно расставить 5 фишек на этой доске так, чтобы никакие две из них не видели друг друга?
python
def is_visible(board, x, y):
# проверяем по горизонтали
for i in range(5):
if board[i][y] == 1:
return True
# проверяем по вертикали
for j in range(5):
if board[x][j] == 1:
return True
# если ни по горизонтали, ни по вертикали не нашли фишку
return False
python
def count_arrangements(board, row, count):
# базовый случай: если прошли все строки, увеличиваем счетчик вариантов на 1
if row >= 5:
return count + 1
# проверяем все клетки в строке
for col in range(5):
# если клетка пуста и фишка не видит других фишек
if board[row][col] == -1 and not is_visible(board, row, col):
# ставим фишку на доску и рекурсивно вызываем функцию для следующей строки
board[row][col] = 1
count = count_arrangements(board, row+1, count)
# после возвращения из рекурсии убираем фишку, чтобы проверить другие варианты
board[row][col] = -1
return count
python
board = [[-1, -1, -1, -1, -1],
[-1, -1, -1, -1, -1],
[-1, -1, -1, -1, -1],
[-1, -1, -1, -1, -1],
[-1, -1, -1, -1, -1]]
count = count_arrangements(board, 0, 0)
Нажимая «Регистрация» или «Войти через Google», вы соглашаетесь с Публичной офертой, даете Согласие на обработку персональных данных, а также подтверждаете что вам есть 18 лет
Нажимая «Регистрация» или «Войти через Google», вы соглашаетесь с Публичной офертой, даете Согласие на обработку персональных данных, а также подтверждаете что вам есть 18 лет