競技プログラミング風 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次元配列を用いるものとする （マス内の数字は配列インデックスを表す）。

[java] #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 に黒石をおいたとき８方向それぞれに白石を挟んでいれば反転
// 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;
}
[/java]

両端キュー（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 で末尾位置の次を示すものとする（下図参照）。

[java] #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;
}
[/java]