Ежедневная часть (e) C++ # 30, Распространенная проблема на собеседовании: Самый длинный возрастающий путь
Сегодня мы рассмотрим распространенную задачу интервью C++: самый длинный возрастающий путь.
Для заданной матрицы, в которой каждый элемент имеет целочисленное значение, вернуть длину самого длинного возрастающего пути, то есть пути, в котором значение каждого элемента строго больше, чем у предыдущих элементов пути. Соседями считаются только ортогонально смежные элементы (т. е. без диагоналей).
В этом примере самый длинный путь — {1, 2, 4, 7, 8, 9}. Прежде чем вы продолжите читать решение, я рекомендую вам попробовать решить его самостоятельно. Вот ссылка на Compiler Explorer с парой тестов: https://compiler-explorer.com/z/hPTMbPa1e.
Решение
Первое осознание состоит в том, что нам не нужно заботиться о циклах, какой бы подход мы ни выбрали. Поскольку значения путей строго возрастают, они никогда не могут вернуться назад.
Это дает нам возможность использовать идею топологического рода. В нашем случае мы можем начать с узлов, у которых нет исходящих путей (то есть с концов наших путей), исследуя пути в обратном направлении, обновляя количество исходящих путей для соседних узлов. Как только узел достигает нуля исходящих путей, он становится концом подпути и добавляется в очередь узлов для исследования.
Наконец, нам нужно отслеживать лучший подпуть в процессе исследования.
int longestPath(const std::vector<std::vector<int>>& matrix) {
// Helper comparator (to avoid re-checking boundaries)
auto less = [&matrix](Coord left, Coord right) {
if (left.ridx < 0 || right.ridx < 0)
return false;
if (left.cidx < 0 || right.cidx < 0)
return false;
if (left.ridx >= std::ssize(matrix) ||
right.ridx >= std::ssize(matrix))
return false;
if (left.cidx >= std::ssize(matrix[left.ridx]) ||
right.cidx >= std::ssize(matrix[right.ridx]))
return false;
return matrix[left.ridx][left.cidx] <
matrix[right.ridx][right.cidx];
};
// Helper that returns the 4 neighbours of a coordinate
auto neighbours = [](Coord c) {
return std::array<Coord,4>(
{{c.ridx-1,c.cidx},{c.ridx,c.cidx-1},
{c.ridx+1,c.cidx},{c.ridx,c.cidx+1}});
};
// We need the number of univisited paths for each element
std::vector<std::vector<std::pair<int,int>>> counts(matrix.size());
// And a queue for the topological sort
std::queue<std::tuple<ptrdiff_t,ptrdiff_t,int>> tails;
for (ptrdiff_t ridx = 0; ridx < std::ssize(matrix); ridx++) {
for (ptrdiff_t cidx = 0; cidx < std::ssize(matrix[ridx]); cidx++) {
counts[ridx].push_back({
// how many neighbours are higher values
std::ranges::count_if(
neighbours({ridx,cidx}),
std::bind_front(less, Coord{ridx,cidx})),
// initial best path
1});
// if this is a terminal node (no neighbours with higher values)
// add it to the queue
if (counts[ridx][cidx].first == 0)
tails.push(std::make_tuple(ridx,cidx,1));
}
}
// topological sort
int max_cnt = 1;
while (!tails.empty()) {
// pick one of the terminal elements
auto [ridx,cidx,len] = tails.front();
tails.pop();
// try to extend the path to a lower number
for (auto &n : neighbours({ridx,cidx})) {
if (!less(n, {ridx,cidx})) continue;
// decrease the number of unvisited paths
counts[n.ridx][n.cidx].first--;
// update the best path for this element
counts[n.ridx][n.cidx].second =
std::max(counts[n.ridx][n.cidx].second, len+1);
// and overall
max_cnt = std::max(max_cnt, counts[n.ridx][n.cidx].second);
// if there are no unvisited paths remaining
// add this element to the queue
if (counts[n.ridx][n.cidx].first == 0)
tails.push(std::make_tuple(n.ridx, n.cidx,
counts[n.ridx][n.cidx].second));
}
}
return max_cnt;
}
Откройте решение в Compiler Explorer.
Сложность этого решения равна O(m*n), где m и n — размеры матрицы. Каждый узел добавляется в очередь один раз (как только количество его исходящих путей достигает нуля), а максимальное количество исходящих путей для каждого узла равно четырем (для общего числа уменьшений).
