torus711 のアレ

主に競技プログラミングの問題について書きます

TopCoder SRM 590, Division 2, Level 1 : FoxAndGomoku

概要

'.' と '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 );
		}
	}
}