競技プログラミング風 C++問題集【第11回】


目次

クローズド・ナイト・ツアー(難易度:★★★★☆)

問題

チェスのナイトは上下左右4方向に2マス進んで、進行方向左に1マスまたは右に1マス、合計8箇所に進むことができる。 将棋の桂馬は2箇所に進むことができるので、チェスのナイトは「八方桂」とも呼ばれる(下図参照)。

競技プログラミング風C++問題集【第11回】_01

wd x ht の盤面において、ナイトを動かして各マスを全て通り、かつ元に戻ってくる問題を「クローズド・ナイト・ツアー」と呼ぶ。

本問題の盤面データ構造は下図のような1次元配列を使用し(マス内の数字は配列インデックス)、 処理を高速化するために、各マスから移動可能なマスをその下のように予め計算し、m_connects に格納しておくものとする。

競技プログラミング風C++問題集【第11回】_02

上記を理解した上で、以下のメンバ関数を実装し、クローズド・ナイト・ツアーの解の数を計算可能にしなさい。

・盤面幅・高さを引数で受け取り、クローズド・ナイト・ツアーの解の数を返すメンバ関数 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++が好き。迷走中・・・ ボードゲーム・パズル系アプリ開発・リリースしてます。
  • このエントリーをはてなブックマークに追加

PAGE TOP