2003dc
Problem C: Secret Number 秘密の数字
マトリックスの中にある秘密の数字を探す。探し方はマス目を右と下にしか移動できない。数字だけをたどっていって、一番大きな数字が「秘密の数字」。
入力
- まずマトリックスの縦(W)と横(H)。0と0で終了。
- 続いてマトリックスの英数字。
再帰を使ってしらみつぶしに探索したら出来たと思ったけど、秘密の数字を整数型で保持できないことに気づく。数字が大きすぎ。文字列で保持しないといけない。
動的計画法を用いるといいらしい。左上からラスタ走査し、上と左に数字があったらカウントして表に入れていく。この表を使うと何とかなりそうだが、できていない。