概要
'.' と 'o' からなるグリッド状の盤面が与えられる。
盤面上で、縦・横・斜めのいずれかに 'o' が五つ並んでいる箇所があるかどうか判定せよ。
解法
開始点と方向で全探索です。
コード
typedef vector<int> VI; typedef vector<string> VS; #define REP( i, m, n ) for ( int i = (int)( m ); i < (int)( n ); ++i ) #define PB( n ) push_back( n ) class FoxAndGomoku { public: int H, W; VS board; VI dy, dx; string win( vector <string> board ) { H = board.size(), W = board[0].size(); this -> board = board; REP( i, -1, 2 ) { REP( j, -1, 2 ) { if ( i == 0 && j == 0 ) { continue; } dy.PB( i ); dx.PB( j ); } } REP( i, 0, H ) { REP( j, 0, W ) { REP( d, 0, dx.size() ) { if ( check( i, j, d, 0 ) ) { return "found"; } } } } return "not found"; } bool check( int y, int x, int d, int l ) { if ( l >= 5 ) { return true; } if ( !( 0 <= y && y < H && 0 <= x && x < W ) ) { return false; } if ( board[y][x] != 'o' ) { return false; } else { return check( y + dy[d], x + dx[d], d, l + 1 ); } } }