Entries

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

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

コメント

[C21]

通れないマスの判定を工夫について教えてください。
  • 2009-09-09 16:05
  • hi
  • URL
  • 編集

[C22]

書いてみただけで実は何も考えていません.
多角形の全ての点から半径m以下の点を通れないとしたのですが,
例えば,多角形の頂点から半径m以下の点と,各辺を幅2m+1の帯だと思って,その点を通れない点とすれば速くなる気がします.
  • 2009-09-09 18:38
  • rsujskf
  • URL
  • 編集

コメントの投稿

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

トラックバック

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

UVa 11656 - Message in the Enemy Territory (この記事を編集する[管理者用])

Source

XXIII Colombian Programming Contest (2009-09-06) (blog)
UVa 11656

問題概要

x軸に平行かy軸に平行な辺のみからなる多角形が与えられる.
その多角形から距離m以下の点は通れない.
ある点からある点まで移動できるかどうかを判定する問題.
点の移動は隣接8点にワープできる感じ.
座標の範囲はx,yともに0以上1000以下.

解法

通れないマスを全て判定したのち,DFSする.
通れないマスの判定を工夫すれば早くなりそうだけど,最も愚直な方法でも通る.

コメント

[C21]

通れないマスの判定を工夫について教えてください。
  • 2009-09-09 16:05
  • hi
  • URL
  • 編集

[C22]

書いてみただけで実は何も考えていません.
多角形の全ての点から半径m以下の点を通れないとしたのですが,
例えば,多角形の頂点から半径m以下の点と,各辺を幅2m+1の帯だと思って,その点を通れない点とすれば速くなる気がします.
  • 2009-09-09 18:38
  • rsujskf
  • URL
  • 編集

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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