No.2064 Smallest Sequence on Grid
レベル : / 実行時間制限 : 1ケース 3.000秒 / メモリ制限
: 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 115
作問者 : とりゐ / テスター : るさ 遭難者 ygussany
タグ : / 解いたユーザー数 115
作問者 : とりゐ / テスター : るさ 遭難者 ygussany
問題文最終更新日: 2022-09-02 21:35:43
問題文
$H$ 行 $W$ 列のマス目があり,上から $i$ 行目,左から $j$ 列目のマス $(i, j)$ には文字 $S_{i,j}$ が書かれています.
以下の操作で長さ $H+W-1$ の文字列を作ることを考えます.
- 最初に空の文字列 $T$ を用意してマス $(1,1)$ に立つ.
-
その後,以下のルールで移動する.
- マス $(H,W)$ にいるとき,文字列 $T$ の最後に文字 $S_{H,W}$ を追加して操作を終了する.
- そうでなければ,今いるマスを $(i,j)$ として,文字列 $T$ の最後に文字 $S_{i,j}$ を追加する.その後,マス $(i+1,j)$ または $(i,j+1)$ に移動する.ただし,マス目の外への移動は許されない.
このような操作によって得られる文字列のうち,辞書順で最小のものを求めてください.
入力
$H\ W$ $S_{1,1}\ \ldots\ S_{1,W}$ $\vdots$ $S_{H,1}\ \ldots\ S_{H,W}$
- $1\leq H,W\leq 3000$
- $H,W$ は整数である
- $S_{i,j}$ は英小文字である
出力
操作によって得られる文字列のうち,辞書順で最小のものを出力してください.
サンプル
サンプル1
入力
3 3 abd dce abd
出力
abcbd
$(1,1)\to(1,2)\to(2,2)\to(3,2)\to(3,3)$ と移動することで文字列 abcbd
が得られます.これが得られる文字列の中で辞書順で最小です.
サンプル2
入力
3 7 yukpbvx znicotf agzsder
出力
yukicoder
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。