Наши слоны Ограничение по времени: 1 секунда Ограничение по памяти: 256 мегабайт На столе лежит шахматная доска, в которой в строк и по столбцов. Слон может ходить по диагонали на…
Наши слоны Ограничение по времени: 1 секунда Ограничение по памяти: 256 мегабайт На столе лежит шахматная доска, в которой в строк и по столбцов. Слон может ходить по диагонали на любое количество клеток. Пустая клетка находится «под боеми, если какой-либо из слонов на доске может одним ходом перейти на эту клетку. На доске в четырёх углах стоят четыре слона. Сколько клеток находится «под боем»? Формат входных данных В первой строке содержится количество строк шахматной доски 11, во второй столбцов m (2≤ n, m ≤10%). Формат выходных данных В единственной строке выведите целое число количество клеток, находящихся: «под боем». Система оценки Решения, правильно работающие при п. 1 < 500, будут оцениваться в 52 балла. Замечание
Чтобы решить задачу, нужно понять, как слоны (шахматные фигуры) атакуют клетки на доске. Слоны могут передвигаться по диагоналям, начиная с каждой из позиций в углах шахматной доски. То есть, если на угловых клетках стоят слоны, они будут угрожать клеткам по диагоналям, проходящим через их позиции.
Шахматная доска имеет четыре угла:
- Верхний левый угол (0,0)
- Верхний правый угол (0, m-1)
- Нижний левый угол (n-1, 0)
- Нижний правый угол (n-1, m-1)
Определим, какие клетки находятся «под боем»:
Диагонали слона в верхнем левом углу (0, 0):
- По диагонали вниз вправо: (1,1), (2,2), ... до (n-1, m-1), пока не выйдешь за границы доски.
- По диагонали вверх вправо: недоступно, так как это верхний край доски.
Диагонали слона в верхнем правом углу (0, m-1):
- По диагонали вниз влево: (1, m-2), (2, m-3), ... до (n-1, 0), пока не выйдешь за границы доски.
- По диагонали вверх влево: недоступно.
Диагонали слона в нижнем левом углу (n-1, 0):
- По диагонали вверх вправо: (n-2, 1), (n-3, 2), ... до (0, m-1).
- По диагонали вниз вправо: недоступно, так как это нижний край доски.
Диагонали слона в нижнем правом углу (n-1, m-1):
- По диагонали вверх влево: (n-2, m-2), (n-3, m-3), ... до (0, 0).
- По диагонали вниз влево: недоступно.
Учитываем относится ли клетка к «под боем»:
Таким образом, мы можем занести все клетки, которые находятся под угрозой, в сетку. Слонам атакуются только те клетки, которые находятся по диагонали от их позиции.
Для получения результата, необходимо узнать общее количество уникальных клеток, находящихся под боем, учитывая, что некоторые из них могут быть засчитаны несколько раз из-за того, что несколько слонов могут угрожать одной и той же клетке.
Пример решения:
Для шахматной доски 11 x m (где m - количество столбцов, равное 11):
- Подсчитаем все клетки, находящиеся под атаками, и проверим на уникальность.
Если ввести ограничение по размерам n и m (например, 2 ≤ n, m ≤ 10), можно легко создать ответ:
Формула подсчета уникальных клеток, находящихся «под боем», будет следующей:
- Для каждой диагонали от слонов, добавляем все клетки на диагонали и проверяем на уникальность или добавляем в множество.
В конечном итоге мы получим количество клеток, находящихся «под боем».
В результате, если выполнены все описанные шаги, будет удобно ввести данные и получить количество клеток, которые под угрозой.
