Напишите функцию, которая возвращает массив окончательных весов всех возможных путей от заданного источника до конца.

Условие найти путь:

  • Вода начнется из источника с весом 100 и будет течь вниз.
  • Когда вода течет вниз, если она попадает в блок, она равномерно разделяется на левую и правую стороны этого блока, 50% влево и 50% вправо.
  • Если поток воды не может течь влево или вправо (либо из-за блока, либо за пределы входного массива), он фактически застревает в структуре и больше не может течь вниз (таким образом, текущий % не достигнет конец).
  • Последняя строка входного массива — это конец, где пути будут взвешены.

Визуализация потока воды сверху вниз поможет вам найти возможные пути от источника и вес воды, который достигнет конца. Эту задачу можно решить как графовую задачу, но здесь мы воспользуемся итеративным методом.

мы делаем источник как -1 в массиве, поэтому мы знаем, что это вода, 0 - свободный путь, 1 - блок, -1 или меньше - вода

Мы начинаем со второй строки, строка выше будет (текущая строка -1), мы перебираем каждый элемент в текущей строке и проверяем, является ли значение в строке выше меньше или равно -1, если правда, мы знаем, что это вода, тогда мы проверяем, равно ли текущее значение 0, если правда, мы просто добавьте указанное выше значение к нашему текущему значению, иначе, если наше текущее значение равно 1, мы знаем, что вода попала на блок, таким образом мы проверяем слева (текущий индекс-1 до 0) и справа (текущий индекс+1 до длины текущей строки) от текущей строки и строка выше, имеет ли она какой-либо путь, т.е. 0, если это правда, то мы обновляем текущую строку с помощью текущее значение + значение строки выше.

Наконец, достигнув конца текущей строки, мы обновляем вышеупомянутую строку текущей строкой и переходим к следующей итерации.

Код доступен здесь.

мы инициализируем первую строку как строку выше, так как мы будем выполнять итерацию, начиная с индекса 1, то есть второй строки.

У нас есть два цикла for: первый будет перебирать каждую строку во входном массиве, а второй будет перебирать все элементы в текущей строке.

мы храним текущую переменную, которая имеет клон текущей строки.

при каждой итерации строки мы обновляем вышеупомянутую строку до текущей переменной.

Наконец, поскольку мы использовали -1 для обозначения веса и воды, мы могли умножить все значения на -100, чтобы получить положительный вес.

Временная сложность составляет O(h * w²), где h — количество строк, а w — количество столбцов, мы проходим по всем строкам один раз, при этом мы проходим по каждому столбцу дважды ( один раз, чтобы проверить каждый элемент в строке, один раз, чтобы проверить левый и правый, если мы наткнулись на блок).

Сложность пространства составляет O(w), где w — количество столбцов в строке, так как мы отслеживаем две строки одновременно.