問題一覧 > 通常問題

No.2064 Smallest Sequence on Grid

レベル : / 実行時間制限 : 1ケース 3.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 103
作問者 : とりゐとりゐ / テスター : るさるさ 遭難者遭難者 👑 ygussanyygussany
2 ProblemId : 6860 / 出題時の順位表 / 自分の提出
問題文最終更新日: 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もしくは右上の雲マークをクリックしてアカウントを作成してください。