第8回オフラインリアルタイムどう書く。C による実装例。

問題 : http://nabetani.sakura.ne.jp/hena/ord8biboma/
解答リンク集 : http://qiita.com/items/709d61dff282cff7a890

当日書いた実装。

ruby版( http://qiita.com/items/0a9fbd1d33ccfd533dc6 )と異なり

• 爆弾ごとにループ
• 方向ごとに関数呼び出し
• 一歩ずつ進める

という方針で、あまりビット演算していない。

solve.c

// compiled with "clang -std=c99"

# include <stdio.h>
# include <string.h>
# include <stdlib.h>

int nibble( char const * hextext, int bit_pos )
{
    char s[2] = { hextext[ bit_pos / 4 ], 0 };
    return strtol( s, 0, 16 );    
}

int mask( int bit_pos )
{
    return 8>>(bit_pos%4);
}

int bit( char const * hextext, int bit_pos )
{
    return !!( nibble( hextext, bit_pos ) & mask( bit_pos ) );
}

int setbit( char * hextext, int bit_pos )
{
    int new_value = nibble( hextext, bit_pos ) | mask( bit_pos );
    hextext[ bit_pos/4 ] = "0123456789abcdef"[new_value];
}

void explode( int bom, int dx, int dy, char const * src, char * result )
{
    if ( bom<0 || 30<bom || bit( src, bom ) ){
        return;
    }
    setbit( result, bom );
    int x=bom%6  +dx;
    int y=bom/6 + dy;
    if ( 0<=x && x<6 && 0<=y && y<5 ){
        explode( bom+dx+dy*6, dx, dy, src, result );
    }
}

void solve( char const * src, char * result  )
{
    strcpy( result, "00000000" );
    for( int bom=0 ; bom<30 ; ++bom ){
        if ( ! bit( src+9, bom ) ){
            continue;
        }
        explode( bom, 0, 1, src, result );
        explode( bom, 0, -1, src, result );
        explode( bom, 1, 0, src, result );
        explode( bom, -1, 0, src, result );
    }
}

void test( char const * src, char const * expected )
{
    char actual[ 9 ] = {0};
    solve( src, actual );
    _Bool ok = 0==strcmp( actual, expected );
    printf( "%s -> %s ( %s ) : %s\n", src, actual, expected, ok ? "ok" : "***NG***" );
}

int main()
{
/*0*/ test( "802b1200/01400c20", "53c40cfc" );
/*29*/ test( "0c901d38/72602200", "f36da280" );
}

いつもどおり、テストデータの大半は省略。

整数を16進数に変換すると言う処理で、sprintf 使うのも嫌だし、strtol の逆の処理の関数思い出せないし、ということでやや乱暴な計算になっている。

あと。関数 bit で行われている !! という演算は2回 not を行う演算で、返戻値を 0 または 1 に強制するためのもの。
http://blog.livedoor.jp/dankogai/archives/51220619.html
で dankogai さんも紹介している。

#include から　solve の最後までで 52行。