競技プログラミング風 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;
}
ヒント
解答例
解説

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

問題

両端キュー(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;
}
ヒント
解答例
解説

関連記事

競技プログラミング風 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