Всем доброй части суток, есть здесь среди задач — вот такая :
Задана квадратная матрица n × n, состоящая из неотрицательных целых чисел. Вам надо найти такой путь на ней, который
начинается в левой верхней ячейке матрицы; каждой следующей ячейкой имеет правую или нижнюю от текущей; заканчивается в правой нижней клетке.
Кроме того, если перемножить все числа вдоль пути и посмотреть на получившиеся произведение, то это число должно быть как можно менее «круглым». Иными словами оно должно заканчиваться на наименьшее возможное количество нулей.
Собственно, как решаю ее я :
Сначала смотрим, что может привести к образованию нулей( а именно множители 2, 5 и число 0 в ячейке матрицы ... )Далее прохожу по всем путям, следуя условию, что двигаться можно либо вниз, либо вправо — делаю это рекурсивно :
Количество делителей записываю в вектора, а сам путь записываю в вектор строк :
int masPath( bool F, std :: string S, uInt X, uInt Y, uInt N, uInt M, uInt M_1 ){
if( Mas[X][Y] == 0 )
F == 1;
if( Mas[X][Y] % 5 == 0 )
M++;
if( Mas[X][Y] % 2 == 0 )
M_1++;
if( X == N - 1 && Y == N - 1 ){
if( !F ){
vec.push_back( M );
vec_1.push_back( M_1 );
}else
vec.push_back( 1 );
vec_2.push_back( S );
return 1;
}
if( X != N - 1 )
masPath( F, S + "D", X + 1, Y, N, M, M_1 );
if( Y != N - 1 )
masPath( F, S + "R", X, Y + 1, N, M, M_1 );
return 0;
}
Затем нахожу минимум, и по его индексу вывожу путь :)
Собственно — программа раблотает вернее верного, все пути как на ладони, но как этого и следовало ожидать — ест столько, что можно лопнуть ( при N = 10 — 5 Mb ), да и постоянный вызов функции — тоже есть доволно много времени ... собственно на 11 тесте у меня ограничение памяти, но даже если его и убрать — т .е как то сократить, то в дальнейшем будет превышение времени ...
Разбор задач, я почитал — и собственно примерно все тоже самое ...Разве что, имеется ввиду какой — то иной способ обхода путей ... Вот у меня и вопрос, какой ?
Заранее благодарю :)
