TopCoder SRM 610, Division 1, Level 1 ( Division 2, Level 2 ) : TheMatrix

問題文

http://community.topcoder.com/stat?c=problem_statement&pm=13035&rd=15843

問題概要

　グリッド状の盤面があり、各セルは白または黒に着色されている。
　二つのセルが接するとは、二つのセルが辺を共有することを言う。領域が Chess Matrix であるとは、同じ色のセルが接していないことを言う。
　盤面内の長方形領域であって、Chess Matrix であるものの面積の最大値を求めよ。

解法

　盤面サイズの縦・横の内大きい方を N と表記します。
　ある長方形領域を決めたとき、その領域が Chess Matrix であるかどうかを定数時間で判定できれば、全体を で解くことができます。可能な Chess Matrrix は、

• 座標の和が奇数のセルが黒、それ以外が白
• 座標の和が偶数のセルが白、それ以外が黒

の二通りしかありません。ある領域が、上記二つの盤面のいずれかの同じ位置と一致したとき、その領域は Chess Matrix であると言えます。これは、上記盤面と一致するセルの数を数えておいて、領域内の全てのセルがいずれかの盤面の対応するセルと一致するかどうかを判定すればよいです。この処理は累積和のテクニックを用いることで判定部分を にできます。累積和の前処理が なので、全体では となり、ちょっときつめですが TL には間に合います。

コード

typedef vector<int> VI;
typedef vector<VI> VVI;

#define REP( i, m, n ) for ( int i = (int)( m ); i < (int)( n ); ++i )
#define FOR( v, c ) for ( auto &v : c )
#define ALL( c ) (c).begin(), (c).end()

class TheMatrix
{
public:
	int MaxArea( vector <string> board )
	{
		const int H = board.size(), W = board[0].size();

		VVI cnts( H, VI( W ) );
		REP( i, 0, H )
		{
			REP( j, 0, W )
			{
				cnts[i][j] = board[i][j] == ( ( i + j ) % 2 ? '1' : '0' );
			}
		}

		VVI csum( H + 1, VI( 1, 0 ) );
		REP( i, 0, H )
		{
			partial_sum( ALL( cnts[i] ), back_inserter( csum[ i + 1 ] ) );
		}

		csum[0] = VI( W + 1 );
		REP( y, 0, H )
		{
			REP( x, 0, W + 1 )
			{
				csum[ y + 1 ][x] += csum[y][x];
			}
		}

		int res = 0;
		REP( y1, 0, H )
		{
			REP( y2, y1, H )
			{
				REP( x1, 0, W )
				{
					REP( x2, x1, W )
					{
						const int n = csum[ y2 + 1 ][ x2 + 1 ] - csum[ y2 + 1 ][ x1 ] - csum[ y1 ][ x2 + 1 ] + csum[ y1 ][ x1 ];
						const int area = ( y2 - y1 + 1 ) * ( x2 - x1 + 1 );
						if ( n == area || !n )
						{
							res = max( res, area );
						}
					}
				}
			}
		}

		return res;
	}
};