Обойти яму
2000 мс · 256 МБ · всё или ничего
В сетке одна клетка провалилась, и наступать на неё нельзя. Из левого верхнего угла надо попасть в правый нижний, двигаясь только вправо и вниз.
Сколько существует путей, обходящих провалившуюся клетку? Она не совпадает ни с началом, ни с концом.
Формат ввода
Одна строка: числа и от до и номера строки и столбца провалившейся клетки, нумерация с единицы.
Формат вывода
Одно число.
Примеры
ввод
3 3 2 2
вывод
2
Примечание
Посчитайте все пути, а потом отнимите те, что проходят через дурную клетку. Путей через клетку ровно столько, сколько путей до неё, умноженное на количество путей от неё.
Войдите, чтобы отправлять решения.