{"problem":{"name":"C. Track","description":{"content":"You already know that Valery's favorite sport is biathlon. Due to your help, he learned to shoot without missing, and his skills are unmatched at the shooting range. But now a smaller task is to be pe","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":5000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF83C"},"statements":[{"statement_type":"Markdown","content":"You already know that Valery's favorite sport is biathlon. Due to your help, he learned to shoot without missing, and his skills are unmatched at the shooting range. But now a smaller task is to be performed, he should learn to complete the path fastest.\n\nThe track's map is represented by a rectangle _n_ × _m_ in size divided into squares. Each square is marked with a lowercase Latin letter (which means the type of the plot), with the exception of the starting square (it is marked with a capital Latin letters _S_) and the terminating square (it is marked with a capital Latin letter _T_). The time of movement from one square to another is equal to 1 minute. The time of movement within the cell can be neglected. We can move from the cell only to side-adjacent ones, but it is forbidden to go beyond the map edges. Also the following restriction is imposed on the path: it is not allowed to visit more than _k_ **different types** of squares (squares of one type can be visited an infinite number of times). Squares marked with _S_ and _T_ have no type, so they are not counted. But _S_ must be visited exactly once — at the very beginning, and _T_ must be visited exactly once — at the very end.\n\nYour task is to find the path from the square _S_ to the square _T_ that takes minimum time. Among all shortest paths you should choose the **lexicographically minimal** one. When comparing paths you should lexicographically represent them as a sequence of characters, that is, of plot types.\n\n## Input\n\nThe first input line contains three integers _n_, _m_ and _k_ (1 ≤ _n_, _m_ ≤ 50, _n_·_m_ ≥ 2, 1 ≤ _k_ ≤ 4). Then _n_ lines contain the map. Each line has the length of exactly _m_ characters and consists of lowercase Latin letters and characters _S_ and _T_. It is guaranteed that the map contains exactly one character _S_ and exactly one character _T_.\n\nPretest 12 is one of the maximal tests for this problem.\n\n## Output\n\nIf there is a path that satisfies the condition, print it as a sequence of letters — the plot types. Otherwise, print \"-1\" (without quotes). **You shouldn't print the character _S_ in the beginning and _T_ in the end**.\n\n**Note that this sequence may be empty.** This case is present in pretests. You can just print nothing or print one \"End of line\"-character. Both will be accepted.\n\n[samples]","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"你知道瓦列里的最爱运动是冬季两项。在你的帮助下，他学会了射击时从不失手，射击水平无人能及。但现在他需要完成一个更小的任务：学会以最快速度完成赛道。\n\n赛道的地图是一个大小为 #cf_span[n × m] 的矩形，被划分为若干方格。每个方格用一个小写拉丁字母标记（表示该地块的类型），但起始方格（用大写拉丁字母 #cf_span[S] 标记）和终止方格（用大写拉丁字母 #cf_span[T] 标记）除外。从一个方格移动到另一个方格所需时间为 #cf_span[1] 分钟，而在方格内部移动的时间可忽略不计。我们只能移动到与当前方格邻接（上下左右）的方格，且不允许移出地图边界。此外，路径需满足以下限制：访问的不同类型方格的总数不得超过 #cf_span[k] 种（同一类型的方格可以被访问无限次）。标记为 #cf_span[S] 和 #cf_span[T] 的方格没有类型，因此不计入类型计数。但 #cf_span[S] 必须恰好访问一次——在路径开始时，而 #cf_span[T] 必须恰好访问一次——在路径结束时。\n\n你的任务是找到从方格 #cf_span[S] 到方格 #cf_span[T] 的耗时最短的路径。在所有最短路径中，你需要选择字典序最小的一条。比较路径时，应将它们视为由地块类型字符组成的序列进行字典序比较。\n\n第一行输入包含三个整数 #cf_span[n]、#cf_span[m] 和 #cf_span[k]（#cf_span[1 ≤ n, m ≤ 50, n·m ≥ 2, 1 ≤ k ≤ 4]）。接下来 #cf_span[n] 行包含地图。每行恰好包含 #cf_span[m] 个字符，由小写拉丁字母以及字符 #cf_span[S] 和 #cf_span[T] 组成。保证地图中恰好包含一个 #cf_span[S] 和一个 #cf_span[T]。\n\n预测试 12 是本题的最大测试用例之一。\n\n如果存在满足条件的路径，请将其作为一串字母（地块类型）输出。否则，输出 \"-1\"（不含引号）。*你不需要在开头输出字符 #cf_span[S]，也不需要在结尾输出字符 #cf_span[T]*。\n\n*注意：该序列可能为空*。这种情况存在于预测试中。你只需不输出任何内容，或输出一个“换行”字符即可，两者均被接受。\n\n## Input\n\n第一行输入包含三个整数 #cf_span[n]、#cf_span[m] 和 #cf_span[k]（#cf_span[1 ≤ n, m ≤ 50, n·m ≥ 2, 1 ≤ k ≤ 4]）。接下来 #cf_span[n] 行包含地图。每行恰好包含 #cf_span[m] 个字符，由小写拉丁字母以及字符 #cf_span[S] 和 #cf_span[T] 组成。保证地图中恰好包含一个 #cf_span[S] 和一个 #cf_span[T]。预测试 12 是本题的最大测试用例之一。\n\n## Output\n\n如果存在满足条件的路径，请将其作为一串字母（地块类型）输出。否则，输出 \"-1\"（不含引号）。*你不需要在开头输出字符 #cf_span[S]，也不需要在结尾输出字符 #cf_span[T]*。*注意：该序列可能为空*。这种情况存在于预测试中。你只需不输出任何内容，或输出一个“换行”字符即可，两者均被接受。\n\n[samples]","is_translate":true,"language":"Chinese"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ n, m, k \\in \\mathbb{Z}^+ $ with $ 1 \\leq n, m \\leq 50 $, $ n \\cdot m \\geq 2 $, $ 1 \\leq k \\leq 4 $.  \nLet $ G = (V, E) $ be a grid graph of size $ n \\times m $, where each cell $ (i, j) $ is a vertex.  \nLet $ \\text{map}[i][j] \\in (\\Sigma \\cup \\{S, T\\}) $ denote the label of cell $ (i, j) $, where $ \\Sigma $ is the set of lowercase Latin letters.  \nLet $ s = (s_i, s_j) \\in V $ be the unique cell with label $ S $.  \nLet $ t = (t_i, t_j) \\in V $ be the unique cell with label $ T $.  \n\n**Constraints**  \n1. Movement is allowed only to 4-directionally adjacent cells (up, down, left, right).  \n2. The path must start at $ s $ and end at $ t $, visiting each exactly once.  \n3. The path may visit any number of cells of the same letter type, but the total number of *distinct* lowercase letter types visited (excluding $ S $ and $ T $) must be at most $ k $.  \n4. The path length (number of edges) is minimized. Among all shortest paths, the lexicographically minimal sequence of *plot types* (i.e., the sequence of lowercase letters visited in order, in the order they are traversed) must be selected.  \n\n**Objective**  \nFind the lexicographically minimal sequence $ P = (c_1, c_2, \\dots, c_\\ell) \\in \\Sigma^* $, where each $ c_i \\in \\Sigma $, such that:  \n- $ P $ is the sequence of plot types (lowercase letters) of the intermediate cells visited along a shortest path from $ s $ to $ t $,  \n- The set $ \\{ c_1, c_2, \\dots, c_\\ell \\} $ has size $ \\leq k $,  \n- If no such path exists, output $-1$.  \n\nThe sequence $ P $ may be empty.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF83C","tags":["graphs","greedy","shortest paths"],"sample_group":[["5 3 2\nSba\nccc\naac\nccc\nabT","bcccc"],["3 4 1\nSxyy\nyxxx\nyyyT","xxxx"],["1 3 3\nTyS","y"],["1 4 1\nSxyT","\\-1"]],"created_at":"2026-03-03 11:00:39"}}