Developer

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

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

目次

オセロ:石反転(難易度:★★★☆☆)

問題

オセロ(リバーシ)盤面と黒着手位置が与えられたとき、縦横斜めに挟まれた白石を黒石に置き換える関数 int putBlack(string& board, int x, y) を実装しなさい。 また、その下請け関数として、インデックス ix 位置にに黒石をおいたとき dir 方向(-10, -9, -8, -1, +1, +8, +9, +10)に白石を挟んでいれば反転し、 反転した白石数を返す関数 int putBlack(int ix, int dir) も実装しなさい。

なお、データ構造としては、下図のように、実際の盤面の外側に番人(壁)を配置する1次元配列を用いるものとする (マス内の数字は配列インデックスを表す)。

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

#include <iostream>       //  標準入出力ライブラリ
#include <string>
using namespace std;    //  std 名前空間使用
#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);
}
typedef unsigned char uchar;
#define     WIDTH       8       //  盤面横幅
#define     HEIGHT      8       //  盤面縦高
#define     ARY_WIDTH   (WIDTH+1)
#define     ARY_SIZE    (ARY_WIDTH*(HEIGHT+2)+1)
#define     EMPTY       0
#define     BLACK       1
#define     WHITE       2
#define     WALL        0xff
class Board {       //  オセロ盤面クラス
public:
    Board() {
        init();
    }
    int xyToIX(int x, int y) const { return x + y * ARY_WIDTH; }    //  x: [1, WIDTH], y: [1, HEIGHT]
    void init() {
        for(auto& x: m_board) x = WALL;     //  一旦全部壁に
        for(int y = 1; y <= HEIGHT; ++y) {
            for(int x = 1; x <= WIDTH; ++x)
                m_board[xyToIX(x, y)] = EMPTY;      //  盤面内を空欄に
        }
        m_board[xyToIX(5, 4)] = m_board[xyToIX(4, 5)] = BLACK;      //  黒石初期配置
        m_board[xyToIX(4, 4)] = m_board[xyToIX(5, 5)] = WHITE;      //  白石初期配置
    }
    void set(const char* ptr) {     //  盤面設定
        for(int y = 1; y <= HEIGHT; ++y) {
            for(int x = 1; x <= WIDTH; ++x) {
                switch( *ptr++ ) {
                case '.': m_board[xyToIX(x, y)] = EMPTY;    break;
                case 'X': m_board[xyToIX(x, y)] = BLACK;    break;
                case 'O': m_board[xyToIX(x, y)] = WHITE;    break;
                }
            }
        }
    }
    string print() const {      //  盤面→表示文字列変換
        string txt;
        for(int y = 1; y <= HEIGHT; ++y) {
            for(int x = 1; x <= WIDTH; ++x) {
                switch( m_board[xyToIX(x, y)] ) {
                case EMPTY: txt += ".";    break;
                case BLACK: txt += "X";    break;
                case WHITE: txt += "O";    break;
                }
            }
            txt += "\n";
        }
        return txt;
    }
    int putBlackDir(int ix, int dir) {      //  黒石着手下請け関数
        //  ToDo: ix に黒石をおいたとき dir 方向に白石を挟んでいれば反転
        //  ToDo: 反転した白石の個数を返す
        return 0;
    }
    int putBlack(int x, int y) {        //  黒石着手関数
        //  ToDo: ix に黒石をおいたとき8方向それぞれに白石を挟んでいれば反転
        //  ToDo: 反転した白石の個数を返す
        return 0;
    }
private:
    uchar   m_board[ARY_SIZE];      //  盤面、周りに番人有り
};
int main() {
    Board bd;
    cout << bd.print() << "\n";
    DO_TEST( bd.putBlack(6, 5) == 1 );
    cout << bd.print() << "\n";
    DO_TEST( bd.print() ==  "........\n"
                            "........\n"
                            "........\n"
                            "...OX...\n"
                            "...XXX..\n"
                            "........\n"
                            "........\n"
                            "........\n" );
    bd.set( "XXXXXXXX"
            "XOOOOOOX"
            "XO.OOOOX"
            "XOOOOOOX"
            "XOOOOOOX"
            "XOOOOOOX"
            "XOOOOOOX"
            "XXXXXXXX" );
    DO_TEST( bd.putBlack(3, 3) == 17 );
    cout << bd.print() << "\n";
    DO_TEST( bd.print() ==  "XXXXXXXX\n"
                            "XXXXOOOX\n"
                            "XXXXXXXX\n"
                            "XXXXOOOX\n"
                            "XOXOXOOX\n"
                            "XOXOOXOX\n"
                            "XOXOOOXX\n"
                            "XXXXXXXX\n" );
    cout << "\nGood Job!\n";
    return 0;
}
ヒント

・着手したい位置が空欄でなければ、着手できないぞ。
・石を挟んで返せるのは、各8方向について、相手の石が続き、次に自分の石がある場合だぞ。

解答例
    int putBlackDir(int ix, int dir) {      //  黒石着手下請け関数
        int cnt = 0;    //  挟まれた相手の石個数
        if( m_board[ix += dir] != WHITE ) return 0;     //  すぐとなりが相手の石でない
        do {
            ++cnt;
        } while( m_board[ix += dir] == WHITE );     //  相手の石が続いている間ループ
        if( m_board[ix] != BLACK ) return 0;        //  自分の石がなければ石を置換しない
        for(int i = 0; i < cnt; ++i)
            m_board[ix -= dir] = BLACK;         //  挟まれた相手の石を黒に置換
        return cnt;
    }
    int putBlack(int x, int y) {        //  黒石着手関数
        int ix = xyToIX(x, y);
        if( m_board[ix] != EMPTY ) return 0;    //  ix が空欄でない場合
        int cnt = putBlackDir(ix, -ARY_WIDTH-1) + putBlackDir(ix, -ARY_WIDTH) + putBlackDir(ix, -ARY_WIDTH+1) +
                putBlackDir(ix, -1) + putBlackDir(ix, 1) +
                putBlackDir(ix, ARY_WIDTH-1) + putBlackDir(ix, ARY_WIDTH) + putBlackDir(ix, ARY_WIDTH+1);
        if( cnt != 0 )      //  挟まれた石があれば
            m_board[ix] = BLACK;    //  着手箇所を黒石にする
        return cnt;
    }
解説

まず、下請けの int putBlackDir(int ix, int dir) の説明から。
引数の ix は着手位置(最初の図参照)で、dir は返す方向だ。左上方向であれば -10, 上方向であれば -9, 右上方向であれば -8、… となる。 石が返るのは、相手の石が続いて、その次が自分の石だった場合だ。なので、回答例の様に do { } while() を使ってコーディングするとよい。 このとき、盤面外に壁があるので、盤面外に出たかどうかの座標チェックの必要がないことに注意してほしい。 相手の石が連続し、その次が自分の石であれば、石が返るのが確定なので、相手の石数をカウントしておき、 ix を戻しながら相手の石を自分の石に置き換える。最後に返した石数を返す。

int putBlack(int x, int y) は、最初に ix 位置が空欄かどうかをチェックし、空欄であれば、 各8方向について先に実装した下請け関数を呼ぶだけだ。 返った石数の合計が0でなければ ix 位置を黒にする。最後に返した石数の合計を返す。

両端キュー(難易度:★★★☆☆)

問題

両端キュー(Deque、デックと発音する)とは先頭または末尾で要素を追加・削除できるキューのことだ。

テストコードの ToDo 部分にコードを追加し、下記のメンバ関数が期待通りに動作するよう実装しなさい。

・先頭データがあれば、その参照を返す T& front()
・末尾データがあれば、その参照を返す T& back()
・先頭にデータを追加する void push_front(T&)
・末尾にデータを追加する void push_back(T&)
・先頭にデータがあれば、それを削除する void pop_front(T&)
・末尾にデータがあれば、それを削除する void pop_back(T&)

なお、データ構造としてはリスト構造ではなく、固定長のリングバッファを用いるものとする。 バッファは固定長なので push_front(), push_front() でバッファに空きが無い場合は、例外をスローするものとする。
また、m_front でキュー内のデータ先頭位置、m_back で末尾位置の次を示すものとする(下図参照)。

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

#include <iostream>       //  標準入出力ライブラリ
#include <string>
using namespace std;    //  std 名前空間使用
#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);
}
template<typename T>
class Deque {
    enum { DFLT_CAPA = 256, };      //  デフォルトキャパシティ
public:
    Deque(size_t capa = DFLT_CAPA)
        : m_capacity(capa)
        , m_size(0)
        , m_front(0)
        , m_back(0)
    {
        m_data = new T[capa];
    }
    ~Deque() {
        delete [] m_data;
    }
    size_t capacity() const {   //  バッファ容量を返す
        return m_capacity;
    }
    bool isEmpty() const {      //  キューが空か?
        return m_size == 0;
    }
    size_t size() const {       //  キューのデータ数を返す
        return m_size;
    }
    void clear() {      //  キューのデータをクリア
        m_size = 0;
        m_back = m_front;
    }
    T& front() {        //  キュー先頭要素への参照を返す
        if (isEmpty()) {
            throw "Exception : no front\n";
        }
        return m_data[0];   //  ToDo: ここを修正し、両端キュー先頭要素への参照を返す
    }
    T& back() {     //  キュー末尾要素への参照を返す
        if (isEmpty()) {
            throw "Exception : no back\n";
        }
        return m_data[0];   //  ToDo: ここを修正し、両端キュー末尾要素への参照を返す
    }
    void push_back(T v) {       //  要素をキュー末尾に追加
        if( m_size == m_capacity ) {
            throw "Exception : out of capacity\n";
        }
        //  ToDo: ここにコードを追加し、キュー末尾に v を追加する
    }
    void push_front(T v) {      //  要素をキュー先頭に追加
        if( m_size == m_capacity ) {
            throw "Exception : out of capacity\n";
        }
        //  ToDo: ここにコードを追加し、キュー先頭に v を追加する
    }
    void pop_back() {       //  キュー末尾要素削除
        //  ToDo: ここにコードを追加し、キュー末尾要素を削除
    }
    void pop_front() {      //  キュー先頭要素削除
        //  ToDo: ここにコードを追加し、キュー先頭要素を削除
    }
private:
    size_t  m_size;         //  両端キュー要素数
    size_t  m_capacity;     //  両端キューキャパシティ
    size_t  m_front;        //  キュー先頭データ位置
    size_t  m_back;         //  キュー末尾データ位置
    T*      m_data;         //  キューデータ用リングバッファ
};
int main() {
    Deque<int> q;
    DO_TEST(q.isEmpty() );
    DO_TEST( q.size() == 0 );
    q.push_back(123);
    DO_TEST(!q.isEmpty());
    DO_TEST(q.size() == 1);
    DO_TEST(q.front() == 123);
    DO_TEST(q.back() == 123);
    q.push_back(12);
    DO_TEST(q.size() == 2);
    DO_TEST(q.front() == 123);
    DO_TEST(q.back() == 12);
    q.push_back(34);
    DO_TEST(q.size() == 3);
    DO_TEST(q.front() == 123);
    DO_TEST(q.back() == 34);
    q.pop_back();
    DO_TEST(q.size() == 2);
    DO_TEST(q.front() == 123);
    DO_TEST(q.back() == 12);
    q.pop_front();
    DO_TEST(q.size() == 1);
    DO_TEST(q.front() == 12);
    DO_TEST(q.back() == 12);
    q.pop_back();
    DO_TEST(q.isEmpty());
    DO_TEST(q.size() == 0);
    cout << "\nGood Job!\n";
    return 0;
}
ヒント

・m_front はキューの先頭位置を示すので、front() は m_data[m_front] を返すといいぞ。
・m_back はキュー末尾位置の次を示すので、back() は m_data[(m_back-1)%m_capacity] を返すといいぞ。
・push_back(d) は、m_back の位置にデータを格納するんだぞ。
・push_front(d) は、m_front の直前位置にデータを格納するんだぞ。
・pop_back() は、m_back をひとつ前に戻すんだぞ。
・pop_front() は、m_front をひとつ先に進めるんだぞ。

解答例
    T& front() {        //  キュー先頭要素への参照を返す
        if (isEmpty()) {
            throw "Exception : no front\n";
        }
        return m_data[m_front];
    }
    T& back() {     //  キュー末尾要素への参照を返す
        if (isEmpty()) {
            throw "Exception : no back\n";
        }
        return m_data[(m_back - 1)%m_capacity];
    }
    void push_back(T v) {       //  要素をキュー末尾に追加
        if( m_size == m_capacity ) {
            throw "Exception : out of capacity\n";
        }
        m_data[m_back] = v;
        m_back = (m_back + 1) % m_capacity;     //  m_back をひとつ進める
        ++m_size;
    }
    void push_front(T v) {      //  要素をキュー先頭に追加
        if( m_size == m_capacity ) {
            throw "Exception : out of capacity\n";
        }
        m_front = (m_front - 1) % m_capacity;   //  m_front をひとつ戻す
        m_data[m_back] = v;
        ++m_size;
    }
    void pop_back() {       //  キュー末尾要素削除
        if (isEmpty()) return;
        m_back = (m_back - 1) % m_capacity;     //  m_back をひとつ戻す
        --m_size;
    }
    void pop_front() {      //  キュー先頭要素削除
        if (isEmpty()) return;
        m_front = (m_front + 1) % m_capacity;       //  m_front をひとつ進める
        --m_size;
    }
解説

m_front がキュー内データの先頭位置を示すので、font() は m_data[m_front] を返すだけだ。 ただし、データが空の場合は例外をスローするようにしている。

m_back がキュー内データの末尾位置の次を示すので、back() は m_data[(m_back-1)%m_capacity] を返すだけだ。 バッファはリングバッファで前後がつながっているとみなすので、m_back-1 だけではだめで、バッファサイズの剰余をとっている。 また front() 同様に、データが空の場合は例外をスローするようにしている。

push_back(d) は、m_back の位置にデータを格納する。ただし、バッファがいっぱいで追加できない場合は例外をスローする。 また、m_back をひとつ進めるのだが、リングバッファは前後がつながっているので m_capacity で剰余をとっておく。 あと、m_size をインクリメントするのを忘れずに。

push_back(d) は、m_front のひとつ前の位置にデータを格納する。リングバッファなので (m_front-1)%m_capacity 位置となる。 あとは push_back() の場合とほぼ同様だ。

pop_back() は、m_back をひとつ前に移動する。ただし、バッファが空であった場合はなにもしない。あと、m_size のデクリメントを忘れずに行う。

pop_front() は、m_front をひとつ前に移動する。pop_back() 同様に、バッファが空であった場合はなにもしないし、m_size のデクリメントを忘れずに行う。

競技プログラミング風 標準C++ライブラリ入門 連載目次リンク

競技プログラミング風 標準C++ライブラリ入門 連載目次

筆者:津田伸秀
プロフィール:テニス・オセロ・ボードゲーム・パズル類が趣味の年齢不詳のおじさん。 自宅研究員(主席)。vi と C++が好き。迷走中・・・ ボードゲーム・パズル系アプリ開発・リリースしてます。