Попытка к бегству

Узник пытается бежать из замка, который состоит из N∗M квадратных комнат, расположенных в виде прямоугольника N∗M. Между любыми двумя соседними комнатами есть дверь, однако некоторые комнаты закрыты и попасть в них нельзя. В начале узник находится в левой верхней комнате и для ему надо попасть в противоположную правую нижнюю комнату. Времени у него немного, всего он может побывать не более, чем в N+M−1 комнате на своем пути. Определите количество маршрутов, которые ведут к выходу.

Входные данные

Первая строчка входных данных содержит натуральные числа N и M, не превосходящие 1000. Далее идет план замка в виде N строчек из M чисел в каждой. Одно число соответствует одной комнате: 1 означает, что в комнату можно попасть, 0 – что комната закрыта.

Выходные данные

Программа должна напечатать количество маршрутов, ведущих узника к выходу и проходящих через M+N−1 комнату, или слово Impossible, если таких маршрутов не существует.

Входные данные подобраны таким образом, что искомое число маршрутов не превосходит 2∗10^9.

Примеры
Ввод
3 5
1 1 1 1 1
1 0 1 0 1
1 1 1 1 1
Вывод
3

История ИИТ начинается с середины 1970-х годов и связывается с совместным практическим применением интеллектуальных информационных систем, систем искусственного интеллекта, систем поддержки решений и информационных систем. История ИИТ связана также с развитием трех научных направлений: компьютерной философии, компьютерной психологии и продвинутой компьютерной науки (Advanced computer science) и дополняется прогрессом в создании:

Объяснение:

1.      ситуационных центров

2.   информационно-аналитических систем

4.  систем поддержки общения человека с компьютером на естественном языке

#include <iostream>

#include <random>

#define INT_MIN -50

#define INT_MAX 50

int main()

{

setlocale(0, "ru");

std::cout << "Введите размер массива: ";

unsigned size{};

std::cin >> size;

int* parr{ new int[size] };

std::default_random_engine generator;

std::uniform_int_distribution<int> distribution(INT_MIN, INT_MAX);

for (unsigned i = 0u; i < size; i++)

{

 parr[i] = distribution(generator);

 std::cout << parr[i] << '\t';

}

std::cout << "\nВведите число: ";

int num{}, sum{}, min = INT_MAX;

std::cin >> num;

for (unsigned i = 0u; i < size; i++)

{

 if (!(parr[i] % 5) && parr[i] > num)

  sum += parr[i];

 if (parr[i] > 0 && min > parr[i])

  min = parr[i];

}

std::cout << "\nСумма чисел больших введенного числа и кратных 5: " << sum << std::endl;

std::cout << "Наименьшее число среди положительных: " << min << std::endl;

delete[] parr;

return 0;

}