1417. Ход ферзя

На доске m × n стоит ферзь. Определите, сколько клеток находится под боем ферзя.

Вход. Четыре натуральных числа: размеры доски m и n и координаты ферзя x и y (1 ≤ x ≤ m ≤ 10⁹, 1 ≤ y ≤ n ≤ 10⁹).

Выход. Выведите количество клеток под боем ферзя.

Пример входа	Пример выхода
8 8 4 5	27

РЕШЕНИЕ

математика

Анализ алгоритма

Ферзь – это шахматная фигура, которая ходит (и бьет) по горизонтали и вертикали.

Строка, в которой стоит ферзь, содержит n клеток. Следовательно количество клеток, на которое ферзь может пойти горизонтальным ходом, равно n – 1. Столбец, в котором стоит ферзь, содержит m клеток. Следовательно количество клеток, на которое ферзь может пойти вертикальными ходом, равно m – 1. То есть под горизонтальным и вертикальным ударом ферзя находится n – 1 + m – 1 клеток.

Разобьем доску на 4 части горизонтальной и вертикальной прямой, проходящей через клетку с ферзем. В каждой такой части подсчитаем количество клеток под ударом.

Рассмотрим например правую верхнюю четверть. Ее длина составляет n – y клеток, а ширина x – 1 клеток. Следовательно клеток под боем ферзя будет min(x – 1, n – y). Аналогично для:

· левой верхней четверти под боем ферзя будет min(x – 1, y – 1) клеток;

· левой нижней четверти под боем ферзя будет min(m – x, y – 1) клеток;

· правой нижней четверти под боем ферзя будет min(m – x, n – y) клеток;

Пример

Рассмотрим пример, в котором размер доски равен 8 × 8, а ферзь находится в позиции (4, 5).

Под горизонтальным и вертикальным ударом ферзя находится n – 1 + m – 1 = 7 + 7 = 14 клеток. Рассмотрим четыре четверти. Под боем ферзя будет находиться:

· в левой верхней четверти min(4, 3) = 3 клетки;

· в левой нижней четверти min(4, 4) = 4 клетки;

· в правой нижней четверти min(3, 4) = 3 клетки;

· в правой верхней четверти min(3, 3) = 3 клетки;

Всего под боем ферзя находится 14 + 3 + 4 + 3 + 3 = 27 клеток.

Реализация алгоритма

Читаем входные данные.

scanf("%d %d %d %d", &m, &n, &x, &y);

Заносим в переменную s количество клеток, которое бьет ферзь горизонтальными и вертикальными ходами.

s = m - 1 + n - 1; // horiz & vertical

Добавляем диагональные клетки, находящиеся под ударом.

s += min(m - x, n - y); // (x,y) = (m, n)

s += min(m - x, y - 1); // (x,y) = (m, 1)

s += min(x - 1, n - y); // (x,y) = (1, n)

s += min(x - 1, y - 1); // (x,y) = (1, 1)

Выводим ответ.

printf("%lld\n",s);