Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

SRM564 DIV1 EASY - KnightCircuit2 (この記事を編集する[管理者用])

Source

TopCoder SRM564 DIV1 EASY (250pt)
Problem Statement

問題概要

W*H (45000*45000以下) のチェス盤を考える.
ナイトを好きなセルにおいて,自由にナイトの動きにそって動かして,元のセルに戻ってくる.
同じセル(最初のセルを含む)を何回訪れても良い.
訪れた(異なる)セルの数の最大値を求める問題.

解法

手を動かして規則を探す.
min(W, H) = 1なら1セルのみ.
min(W, H) = 2なら,(max(W, H) + 1) / 2セル.
W = H = 3なら8セル.(中央以外)
それ以外なら全部のセルを訪れることができる.

C++によるスパゲッティなソースコード
// #includeとusing namespace std;は略

class KnightCircuit2 {
public:
int maxSize(int w, int h) {
  int i, j, k;

  if(w > h) k = w, w = h, h = k;
  if(w==1) return 1;
  if(w==2) return (h+1)/2;
  if(w==3 && h==3) return 8;

  return w*h;
}

};

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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