Попытка к бегству
Узник пытается бежать из замка, который состоит из 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
<p>program xxx;</p><p> var i, k, d, e, s : integer;</p><p>begin</p><p> k:=0;</p><p> for i:= 10 to 99 do</p><p> begin</p><p> d:= i div 10;</p><p> e:= i mod 10;</p><p> s:=d + e;</p><p> if i mod s = 0 then k:=k+1</p><p> end;</p><p> write ('кол-во чисел которые делятся на сумму своих цифр=', k);</p><p> readln</p><p>end.</p>
Var a1,a2,a3,a4,t1,t2,t3,p,d,vp,b: Integer;
begin
writeln ('программа вычисляет норму для данного ученика');
writeln ('введи массу учебника 1');readln (a1);
writeln ('введи массу учебника 2');readln (a2);
writeln ('введи массу учебника 3');readln (a3);
writeln ('введи массу тетради 1');readln (t1);
writeln ('введи массу тетради 2');readln (t2);
writeln ('введи массу тетради 3');readln (t3);
writeln ('введи массу пенала');readln (p);
writeln ('введи массу дневника');readln (d);
writeln ('введи массу портфеля');readln(vp);
b:=a1+a2+a3+a4+t1+t2+t3+p+d+vp;writeln ('общая масса портфеля= ' b);
if (b<=5) then writeln ('норма') else writeln ('ненорма');
readln;
end.