На одном из стендов на столе в квадратной матрице 5х6 клеток размещён робот. В начале эксперимента он находится в левой верхней клетке Ѕ. Робот умеет перемещаться за один ход на одну клетку вправо или на одну клетку вниз. Роботу нужно добраться до правой нижней клетки F. К сожалению, в клетки Х с координатами (2, 3) и У с координатами (5, 4) была пролита кислота, и если робот попадет в какую-либо из них, то сразу же сломается и не сможет доехать до финиша F. Перед запуском эксперимента исследователям стало интересно: сколькими способами робот может добраться из клетки 5 в клетку F, не попадая в клетки Х и Ү?

Для решения данной задачи можно воспользоваться методом динамического программирования.

Обозначим количество способов добраться до клетки (i, j) как dp[i][j]. Тогда для клетки (i, j) количество способов равно сумме количества способов из клеток (i-1, j) и (i, j-1), если клетка (i, j) не является клеткой Х или У. Иначе количество способов равно 0.

Исходя из этого, можно заполнить матрицу dp по следующему принципу:

dp[1][1] = 1 dp[2][3] = dp[5][4] = 0

Далее, для всех остальных клеток (i, j) вычисляем значение dp[i][j] по формуле:

dp[i][j] = dp[i-1][j] + dp[i][j-1], если клетка (i, j) не является клеткой Х или У dp[i][j] = 0, если клетка (i, j) является клеткой Х или У

Таким образом, после заполнения матрицы dp, значение dp[5][6] будет содержать количество способов добраться из клетки (1, 1) в клетку F, не попадая в клетки Х и У.