Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

UVa 12336 - Knights in the Zombie Land (この記事を編集する[管理者用])

Source

ACM ICPC Regional Warmup 2011 (2011-10-29)
UVa 12336

問題概要

R*C (100000*100000以下) のチェス盤があり,使えないセルがn個 (10^5以下) 与えられる.
4個の駒a, b, c, dを以下の条件をみたすように置くパターンの数を求める問題.
 aとbはナイトの移動方法でちょうど1回で移動できる場所
 bとcはナイトの移動方法でちょうど1回で移動できる場所
 cとdはナイトの移動方法でちょうど1回で移動できる場所
 dとaはナイトの移動方法でちょうど1回で移動できる場所
 aとcはナイトの移動方法でちょうど1回で移動できないる場所
 bとdはナイトの移動方法でちょうど1回で移動できないる場所

解法

4つの駒の位置関係は6通りぐらいしかない.
使えないセルがない場合のパターン数は,その位置関係のバウンディングボックスを配置できるx座標の値の範囲,y座標の値の範囲を独立に求めてかけることで求まる.
後は,使えないセルを使ってしまうパターン数を数えて,引けば良い.

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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