Entries

スポンサーサイト (この記事を編集する[管理者用])

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

コメント

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://rsujskf.blog32.fc2.com/tb.php/2230-7bd145fe
この記事にトラックバックする(FC2ブログユーザー)

SPOJ 9921 - ABC Path [ABCPATH] (この記事を編集する[管理者用])

Source

FCIS Local Contest 2012
SPOJ 9921 [ABCPATH]

問題概要

50*50以下のグリッドが与えられ,各セルには,アルファベット大文字が一文字書かれている.
上下左右斜めに隣接しているとみなす.
Aの書かれているセルから始まるパスで,アルファベット順にA, B, C, ...と続くパスを考える.(ZからAには戻れない)
その中で最長のものの長さを求める問題.

解法

BFSやDPなどで,辿りつけるマスを求めておく.
後は,辿りつけるマスのうち最も大きいアルファベットのマスが答え.

コメント

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://rsujskf.blog32.fc2.com/tb.php/2230-7bd145fe
この記事にトラックバックする(FC2ブログユーザー)

Appendix

Recent Articles

ブログ内検索

Ads


(プライバシーポリシー)
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。