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

9×9の通常サイズの数独（「数独」は株式会社ニコリの登録商標です）の盤面情報を持つ１次元配列と、マス目位置（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 を返す。

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

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

・各マスには数字 ‘1’～’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;
}

short getCanPlacedNums(const short board[], int x, int y) {
    if (board[x + y * WD] != EMPTY) return 0;   //  空欄でない場合
    short bits = 0;     //  配置済み数字ビット
    for (int i = 0; i != WD; ++i)   //  縦横方向配について
        bits |= board[i + y * WD] | board[x + i * WD];  //  配置済み数字ビット更新
    int x0 = x - x % BWD;   //  3x3ブロック左端位置
    int y0 = y - y % BWD;   //  3x3ブロック上端位置
    for (int v = 0; v != BWD; ++v) {    //  3x3ブロック内の各位置について
        for (int h = 0; h != BWD; ++h)
            bits |= board[x0 + h + (y0 + v) * WD];  //  ブロック内数字  配置済み数字ビット更新
    }
    return ALL ^ bits;  //  配置済み数字を反転することで配置可能数字ビットを返す
}