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


目次

数独(難易度:★★★☆☆)

問題

9×9の通常サイズの数独(「数独」は株式会社ニコリの登録商標です)の盤面情報を持つ1次元配列と、マス目位置(x, y)を引数で渡され、 指定された箇所にどの数字が配置可能かを返す関数 short getCanPlacedNums(const short board[], int x, int y) を実装しなさい。

ただし、各マスの値は、空欄は0, 数値: 1を「数値-1」回左にシフトした値とする (1: 0x0001, 2: 0x0002, 3: 0x0004, 4: 0x0008, … 9: 0x0100)。
関数が返す値も上記のビット値のビット和とする。例えば、3と5が配置可能な場合は 0x0004 | 0x0010 = 0x0014 を返す。

また、x, y は 0 ~ 8 の範囲とし、左上が原点(0, 0)とする。

例えば、盤面が下図の場合、(2, 1) には、3, 5, 8, 9 を入れることができるので、getCanPlacedNums(board, 2, 1) は 0x0004 | 0x0010 | 0x0080 | 0x0100 = 0x0194 を返す。

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

1次元配列中のデータの順序は、左から右、上から下の順序とする。

なお、知っている人がほとんだだとは思うが、念の為に数独ルールを以下に示しておく。

・各マスには数字 ‘1’~’9′ を入れる。
・横9マス・縦9マス・(上図の太線部分の)3×3ブロック内には同じ数字を入れない。

#include <iostream>       //  標準入出力ライブラリ
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);
}
#define     EMPTY       0
#define     NUM_1       0x0001
#define     NUM_2       0x0002
#define     NUM_3       0x0004
#define     NUM_4       0x0008
#define     NUM_5       0x0010
#define     NUM_6       0x0020
#define     NUM_7       0x0040
#define     NUM_8       0x0080
#define     NUM_9       0x0100
#define     WD          9
#define     BWD         (WD/3)
#define     ALL             ((1<<WD)-1)
void set(short* board, const char* ptr) {
    for (; *ptr != '\0'; ++ptr)
        *board++ = (*ptr >= '1' && *ptr <= '9') ? (1 << (*ptr - '1')) : 0;
}
short getCanPlacedNums(const short board[], int x, int y) {
    //  ToDo: ここに str で指定された地形に貯まる水の面積を返すコードを記述
    return 0;
}
int main() {
    short board[WD*WD];       //  数独盤面
    set(board, "1.28.59.47...6...2...4.9...6.1...5.9.7.....6.8.4...2.1...6.8...4...5...65.61.74.3");
    DO_TEST( getCanPlacedNums(board, 0, 0) == 0 );
    DO_TEST( getCanPlacedNums(board, 1, 1) == (NUM_3|NUM_4|NUM_5|NUM_8|NUM_9) );
    DO_TEST( getCanPlacedNums(board, 2, 4) == (NUM_3|NUM_5|NUM_9) );
    DO_TEST( getCanPlacedNums(board, 8, 4) == (NUM_8) );
    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