Задано таблицу N * M, в каждой ячейке которой написана одна строчная буква английского алфавита. Рассмотрим все возможные пути от левого верхнего угла к правому нижнему углу, если вам разрешено идти только вправо и вниз. Конкатенация букв в процессе движения образует строку. Будем считать, что эта строка — значение пути. Теперь рассмотрим все такие пути и отсортируем их значение в алфавитном порядке. Ваша задача: найти значение I-го пути в этом отсортированном списке.
Формат входных данных
Первая строка входного файла содержит два целых числа N (количество строк) и M (количество столбцов): 1≤N, M≤30. Следующие N строк содержат M строчных букв английского алфавита. Последняя строка входного файла содержит целое число I (1≤I≤1018).
Формат результата
Выходной файл должен содержать одну строку — ответ на задачу.
Примечания
pbbvbzyvt pbbvxeggt pbbvxegvt pbbvxeyvt pbbvxzyvt pbbzveggt pbbzvegvt pbbzveyvt pbbzvrggt pbbzvrgvt pbbzvrzgt pbbzxeggt pbbzxegvt pbbzxeyvt pbbzxzyvt pbhbglzgt pbhbgrggt
pbhbgrgvt pbhbgrzgt pbhbveggt pbhbvegvt pbhbveyvt pbhbvrggt pbhbvrgvt pbhbvrzgt pbhzveggt pbhzvegvt pbhzveyvt pbhzvrggt pbhzvrgvt pbhzvrzgt pbhzxeggt pbhzxegvt pbhzxeyvt pbhzxzyvt pjhbglzgt pjhbgrggt pjhbgrgvt pjhbgrzgt pjhbveggt pjhbvegvt pjhbveyvt pjhbvrggt pjhbvrgvt pjhbvrzgt pjhzveggt pjhzvegvt pjhzveyvt pjhzvrggt pjhzvrgvt pjhzvrzgt pjhzxeggt pjhzxegvt pjhzxeyvt pjhzxzyvt pjzbglzgt pjzbgrggt pjzbgrgvt pjzbgrzgt pjzbveggt pjzbvegvt pjzbveyvt pjzbvrggt pjzbvrgvt pjzbvrzgt pjzwglzgt pjzwgrggt pjzwgrgvt pjzwgrzgt pjzwmlzgt
Моя попытка решить:
1) использовать алгоритм "перебор з возвратом";
2) когда выбирается новый кандидат, то сравниваются символы из допустимых ячеек таблицы (учитывая допустимые направления).
Возникла проблема: а как сделать выбор, если оба направления (вправо, вниз) — допустимые и возможные кандидаты (ячейки таблицы) содержат одинаковые символы?..
Вопрос:
1) можно ли таким алгоритмом решит эту задачу, если "да", то как быть с выбором между одинаковыми кандидатами?
2) какой алгоритм (если указанный мною способ неверен) вместо перебора с возвратом может решить эту задачу эффективнее?
