Программа работает неверно , помогите найти баг
Вот задача,
Вам дана нижнетреугольная матрица из n строк (i-й ряд состоит ровно из i элементов, расположенных в столбцах с номерами от 1 до i). В каждой ячейке матрицы записана маленькая латинская буква. Также у вас есть пустая строка s.
Вы стоите в ячейке с координатами (1, 1) (первая строка, первый столбец). На каждом ходу можно делать переход на одну ячейку ниже или на одну ячейку по диагонали вправо-вниз. То есть из ячейки с координатами (i, j) можно попасть в ячейки (i+1, j) или (i+1, j+1).
Каждый раз, когда вы попадаете в новую ячейку, к строке s в конец приписывается буква, стоящая в этой ячейке. Найдите лексикографически минимальную строку, которую можно получить при переходе из первой строки матрицы в последнюю (n-ю).
Формат входных данных:
В первой строке задано число n (1 ≤ n ≤ 5⋅103).
Затем идёт n строк, в i-й находится строка из i символов, отвечающая первым i столбцам i-й строки матрицы.
Формат результата:
Выведите искомую строку.
Примеры
Входные данные
3
o
nu
mwb
Результат работы
onm
Входные данные
4
a
bb
czc
defr
Слышал , что как-то решается через дп, но не знаю как.
Ещё не проходит тест
4
a
bb
ccc
zzzza
Код
#include<iostream>
#include <vector>
#include <vector>
#include <assert.h>
using namespace std;
typedef long long ll;
vector<vector<char>> a (10000 , vector<char> (10000));
vector<string> nums;
void right(int n) {
string res;
res+=a[1][1];
int idxI = 1;
int idxJ = 1;
for(int i = 1 ; i < n;i++) {
if ((a[idxI + 1][idxJ] < a[idxI + 1][idxJ + 1])) {
res+= a[idxI + 1][idxJ];
idxI++;
}
else {
res+=a[idxI + 1][idxJ + 1];
idxI++;
idxJ++;
}
}
nums.push_back(res);
}
void left(int n) {
string res;
res+=a[1][1];
int idxI = 1;
int idxJ = 1;
for(int i = 1 ; i < n;i++) {
if ((a[idxI + 1][idxJ] < a[idxI + 1][idxJ + 1])) {
res+= a[idxI + 1][idxJ];
idxI++;
} else if(a[idxI + 1][idxJ] == a[idxI + 1][idxJ + 1]){
res+= a[idxI + 1][idxJ];
idxI++;
right(n);
}
else {
res+=a[idxI + 1][idxJ + 1];
idxI++;
idxJ++;
}
}
nums.push_back(res);
}
int main() {
int n;
cin >> n;
for(int i = 1 ; i <= n;i++) {
for(int j = 1; j <= i ;j++) {
scanf(" %c",&a[i][j]);
}
}
left(n);
string res = nums[0];
for(auto x : nums) {
res = min(res , x);
}
cout << res << endl;
return 0;
}
Ответы (1 шт):
Добавим к каждой строке заведомо бОльший символ (например, "z"+1= "{") (это не обязательно, если усложнить проверки для prev ниже)
Создадим вектор best[] длиной n для лучших символов каждой строки (не обязательно меньших, а тех, путь к которым составляет лексикографически наим. строку), в нулевой элемент запишем символ из верхушки a[0][0], остальные заполним всё той же скобкой.
Для каждого элемента остальных строк - смотрим, стоит ли вверху или вверху-слева тот же символ, что записан в предыдущий best (от проверок для последнего и первого символа избавляемся благодаря скобке в конце)
prev = min(a[i-1][(k + i - 1) % i], a[i-1][k]);
Если да, то обновляем best для текущей строки
if (prev == best[i-1])
best[i] = min(best[i], a[i][k]);
Если нет, то текущий символ никак не войдёт в результат, и мы его меняем на скобку, чтобы он не мешал дальше - хотя он и может совпасть с с лучшим по строке, но недостижим по оптимальному пути.
В результате best[] содержит лексикографически минимальную строку.
Код на Python (там s[-1] указывает на последний элемент списка, поэтому (k + i - 1) % i не требуется)
import random
def bestpath(l):
n = len(l)
best = ['{']*n
best[0] = l[0][0]
for i in range(1, n):
for k in range(i+1):
prev = min(l[i-1][k-1], l[i-1][k])
if prev == best[i-1]:
best[i] = min(best[i], l[i][k])
else:
l[i][k] = '{'
return best
l = []
n = 5
for i in range(1,n+1):
l.append([chr(97 + random.randint(0,6)) for _ in range(i)])
l[-1].append('{')
print(''.join(l[-1][:-1]))
print('--------')
print(''.join(bestpath(l)))