目次
クローズド・ナイト・ツアー(難易度:★★★★☆)
問題
チェスのナイトは上下左右4方向に2マス進んで、進行方向左に1マスまたは右に1マス、合計8箇所に進むことができる。 将棋の桂馬は2箇所に進むことができるので、チェスのナイトは「八方桂」とも呼ばれる(下図参照)。
wd x ht の盤面において、ナイトを動かして各マスを全て通り、かつ元に戻ってくる問題を「クローズド・ナイト・ツアー」と呼ぶ。
本問題の盤面データ構造は下図のような1次元配列を使用し(マス内の数字は配列インデックス)、 処理を高速化するために、各マスから移動可能なマスをその下のように予め計算し、m_connects に格納しておくものとする。
上記を理解した上で、以下のメンバ関数を実装し、クローズド・ナイト・ツアーの解の数を計算可能にしなさい。
・盤面幅・高さを引数で受け取り、クローズド・ナイト・ツアーの解の数を返すメンバ関数 int Board::countKnightTour(int wd, int ht)
・ナイトが ix に来た場合、その移動可能先の連結数を増やすメンバ関数 void incNConnect(int ix)
・ナイトが ix に来た場合、その移動可能先の連結数を減らすメンバ関数 bool decNConnect(int ix, int& ix1)
・ナイトが ix 位置にn番目に移動した場合の処理を行うメンバ関数 void KnightTour(int n, int ix)
#include <iostream> // 標準入出力ライブラリ #include <vector> #include <string> using namespace std; // std 名前空間使用 typedef unsigned char uchar; #define DO_TEST(exp) do_test(exp, __LINE__) void do_test(bool b, int line) { if( b ) return; // OK cout << "\nNG at line " << line << "\n"; exit(1); } class Board { public: Board(int wd = 10, int ht = 3) { setSize(wd, ht); } public: inline int xyToIX(int x, int y) const { return x + y * m_BD_WIDTH; } inline bool isInner(int x, int y) const { return x >= 0 && x < m_BD_WIDTH && y >= 0 && y < m_BD_HEIGHT; } void printNth() const { // m_nth[] 盤面表示 for (int y = 0; y < m_BD_HEIGHT; ++y) { for (int x = 0; x < m_BD_WIDTH; ++x) { auto t = to_string((int)m_nth[x+y*m_BD_WIDTH]); if (t.size() < 2) t = ' ' + t; cout << t << " "; } cout << "\n"; } cout << "\n"; } void printConnects() const { // 連結数、連結リスト表示 for (int i = 0; i != m_BD_SIZE; ++i) { cout << i << ": " << (int)m_nConnect[i] << " {"; for (auto& x : m_connects[i]) cout << (int)x << ", "; cout << "}\n"; } cout << "\n"; } void setSize(int wd, int ht) { // サイズ設定 m_BD_WIDTH = wd; m_BD_HEIGHT = ht; m_BD_SIZE = wd * ht; // nth 配列初期化 m_nth.resize(m_BD_SIZE); for(auto& x: m_nth) x = 0; // 連結リスト初期化 m_nConnect.resize(m_BD_SIZE); m_connects.resize(m_BD_SIZE); int ix = 0; for (int y = 0; y < ht; ++y) { for (int x = 0; x < wd; ++x, ++ix) { m_connects[ix].clear(); if (isInner(x - 1, y - 2)) m_connects[ix].push_back(xyToIX(x - 1, y - 2)); if (isInner(x + 1, y - 2)) m_connects[ix].push_back(xyToIX(x + 1, y - 2)); if (isInner(x - 2, y - 1)) m_connects[ix].push_back(xyToIX(x - 2, y - 1)); if (isInner(x + 2, y - 1)) m_connects[ix].push_back(xyToIX(x + 2, y - 1)); if (isInner(x - 2, y + 1)) m_connects[ix].push_back(xyToIX(x - 2, y + 1)); if (isInner(x + 2, y + 1)) m_connects[ix].push_back(xyToIX(x + 2, y + 1)); if (isInner(x - 1, y + 2)) m_connects[ix].push_back(xyToIX(x - 1, y + 2)); if (isInner(x + 1, y + 2)) m_connects[ix].push_back(xyToIX(x + 1, y + 2)); } } // 連結数配列初期化 for (int i = 0; i != m_BD_SIZE; ++i) { m_nConnect[i] = (uchar)m_connects[i].size(); } } // ix に連結しているセルの連結数を減らす // 連結数が1になったセルがあれば、そこに強制移動になるので ix1 にその位置を設定 // 連結数が1になったセル複数ある場合はデッドエンドなので false を返す bool decNConnect(int ix, int& ix1) { // ToDo: ここにコードを追加し、ナイトが ix に来た場合、その移動可能先の連結数を減らす return true; } void incNConnect(int ix) { // ToDo: ここにコードを追加し、ナイトが ix に来た場合、その移動可能先の連結数を増やす } void KnightTour(int n, int ix) { // ToDo: ここにn番目のナイトが ix 位置に移動した場合の処理を追加 } int countKnightTour(int wd, int ht) { return 0; // ToDo: ここにコードを追加し、wd x ht 盤面でのクローズド・ナイト・ツアーの解数を返す } private: int m_count = 0; int m_BD_WIDTH; // 盤面幅 int m_BD_HEIGHT; // 盤面高 int m_BD_SIZE; vector<uchar> m_nth; // 何番目にそのセルを訪れたか(1..盤面サイズ) vector<uchar> m_nConnect; // 各セル連結数 vector<vector<uchar>> m_connects; // 各セルと連結しているセルインデックスリスト }; int main() { Board bd; DO_TEST( bd.countKnightTour(3, 3) == 0 ); DO_TEST( bd.countKnightTour(10, 3) == 16 ); DO_TEST( bd.countKnightTour(3, 10) == 16 ); DO_TEST( bd.countKnightTour(6, 5) == 8 ); DO_TEST( bd.countKnightTour(6, 6) == 9862 ); DO_TEST( bd.countKnightTour(6, 7) == 1067638 ); cout << "\nGood Job!\n"; return 0; }
関連記事

競技プログラミング風 C++問題集【第16回】
目次 0/1ナップサック問題(難易度:★★★★☆) 0/1ナップサック問題(難易度:★★★★☆) 関連記事 筆者:津田伸秀 プロフィール:テニス・オセロ・ボードゲーム・パズル類が趣味の年齢不詳のおじさん。 自宅研究員(主 […]
コメントなし

競技プログラミング風 C++問題集【第15回】
目次 ポーカー:役判定(難易度:★★★☆☆) ポーカー:役判定(難易度:★★★☆☆) 関連記事 筆者:津田伸秀 プロフィール:テニス・オセロ・ボードゲーム・パズル類が趣味の年齢不詳のおじさん。 自宅研究員(主席)。vi […]
コメントなし

競技プログラミング風 C++問題集【第14回】
目次 無向グラフ(難易度:★★★☆☆) 無向グラフ(難易度:★★★☆☆) 関連記事 筆者:津田伸秀 プロフィール:テニス・オセロ・ボードゲーム・パズル類が趣味の年齢不詳のおじさん。 自宅研究員(主席)。vi と C++が […]
コメントなし

競技プログラミング風 C++問題集【第13回】
はじめに 今回から4回にわたって「競技プログラミング風 C++問題集 第13回~第16回(シーズン4)」をお届けする。 各問題は、「問題文」「テストコード」「ヒント」「解答例」「解説」から構成される。 まず、問題を読んで […]
コメントなし

競技プログラミング風 C++問題集【第12回】
目次 文字列比較(難易度:★★★★☆) 文字列比較(難易度:★★★★☆) 関連記事 筆者:津田伸秀 プロフィール:テニス・オセロ・ボードゲーム・パズル類が趣味の年齢不詳のおじさん。 自宅研究員(主席)。vi と C++が […]
コメントなし

競技プログラミング風 C++問題集【第11回】
目次 クローズド・ナイト・ツアー(難易度:★★★★☆) クローズド・ナイト・ツアー(難易度:★★★★☆) 関連記事 筆者:津田伸秀 プロフィール:テニス・オセロ・ボードゲーム・パズル類が趣味の年齢不詳のおじさん。 自宅研 […]
コメントなし

競技プログラミング風 C++問題集【第10回】
目次 オセロ:石反転(難易度:★★★☆☆) 両端キュー(難易度:★★★☆☆) オセロ:石反転(難易度:★★★☆☆) 両端キュー(難易度:★★★☆☆) 関連記事 筆者:津田伸秀 プロフィール:テニス・オセロ・ボードゲーム・ […]
コメントなし

競技プログラミング風 C++問題集【第9回】
はじめに 今回から4回にわたって「競技プログラミング風 C++問題集 第9回~第12回(シーズン3)」をお届けする。 各問題は、「問題文」「テストコード」「ヒント」「解答例」「解説」から構成される。 まず、問題を読んで正 […]
コメントなし

競技プログラミング風 C++問題集【第8回】
目次 文字列クラス(難易度:★★★★☆) 文字列クラス(難易度:★★★★☆) 関連記事 筆者:津田伸秀 プロフィール:テニス・オセロ・ボードゲーム・パズル類が趣味の年齢不詳のおじさん。 自宅研究員(主席)。vi と C+ […]
コメントなし

競技プログラミング風 C++問題集【第7回】
目次 数独(難易度:★★★☆☆) 数独(難易度:★★★☆☆) 関連記事 筆者:津田伸秀 プロフィール:テニス・オセロ・ボードゲーム・パズル類が趣味の年齢不詳のおじさん。 自宅研究員(主席)。vi と C++が好き。迷走中 […]
コメントなし
![]() |
筆者:津田伸秀 プロフィール:テニス・オセロ・ボードゲーム・パズル類が趣味の年齢不詳のおじさん。 自宅研究員(主席)。vi と C++が好き。迷走中・・・ ボードゲーム・パズル系アプリ開発・リリースしてます。 |