目次
オセロ:石反転(難易度:★★★☆☆)
オセロ(リバーシ)盤面と黒着手位置が与えられたとき、縦横斜めに挟まれた白石を黒石に置き換える関数 int putBlack(string& board, int x, y) を実装しなさい。 また、その下請け関数として、インデックス ix 位置にに黒石をおいたとき dir 方向(-10, -9, -8, -1, +1, +8, +9, +10)に白石を挟んでいれば反転し、 反転した白石数を返す関数 int putBlack(int ix, int dir) も実装しなさい。
なお、データ構造としては、下図のように、実際の盤面の外側に番人(壁)を配置する1次元配列を用いるものとする (マス内の数字は配列インデックスを表す)。
#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 で末尾位置の次を示すものとする(下図参照)。
#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++ライブラリ入門 連載目次リンク
![]() |
筆者:津田伸秀 プロフィール:テニス・オセロ・ボードゲーム・パズル類が趣味の年齢不詳のおじさん。 自宅研究員(主席)。vi と C++が好き。迷走中・・・ ボードゲーム・パズル系アプリ開発・リリースしてます。 |