Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

UVa 11906 - Knight in a War Grid (この記事を編集する[管理者用])

Source

A National Bangladeshi Contest (2011-01-09) (blog)
UVa 11906

問題概要

R*C (100*100以下) のチェス盤の上で,とあるナイトが左上のマスにいる.
チェス盤はいくつか移動できないマスが指定されている.
このナイトは1回の移動で水平方向か垂直方向にN (50以下) だけ動いて,別の方向にM (50以下) だけ動く.
通常のナイトはN=1,M=2.
ナイトは自由に移動でき,このナイトが訪れた各マスを色分けしていく.
そのマスに直接移動可能なマスの数が偶数なら白,奇数なら黒く塗る.
辿りつけない場所は色を塗らない.
最終的に白と黒のマスの数を求める問題.

解法

DFSとかして実際に探索しながら数えるだけ.
N=Mのとき,縦にN,横にMと縦にM,横にNを重複して数えないように注意.

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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