概要
の平面があり、平面上の 個の領域が与えられる。
与えられた領域のいずれにも含まれない領域は、与えられた領域によって分割されている。
分割されている領域の数を求めよ。
解法
面積が大きいので、全てをメモリに格納しようとすると MLE してしまいます。
この問題の場合、重要なのは領域の数だけで、面積を計算する必要はないので、無駄な部分を省略することができます。
必要な部分は、各軸の方向に対して、変化のある部分とその前後の行または列だけです。
変化のある部分とは、入力によって与えられた点のある座標です。
軸と 軸に分け、点が存在する部分の前後のみを抽出して平面を構築しなおします。
すると、高さと幅は高々 になるので、メモリに格納することができます。
あとは、よくある塗り潰しの全探索をすれば答えが求まります。
コード
typedef vector<int> VI; typedef vector<VI> VVI; typedef pair<int,int> PII; #define REP( i, m, n ) for ( int i = (int)( m ); i < (int)( n ); ++i ) #define EACH( v, c ) for ( auto &v : c ) #define ALL( c ) (c).begin(), (c).end() #define PB( n ) push_back( n ) #define MP( a, b ) make_pair( ( a ), ( b ) ) #define fst first #define snd second const int dir[][2] = { 1, 0, 0, 1, -1, 0, 0, -1 }; // 座標圧縮 int comp( VI &x1, VI &x2, int W ) { const int N = x1.size(); VI xs; REP( i, 0, N ) { REP( j, -1, 2 ) { // 変化のある座標の前後の座標について、有効な範囲なら追加 int tmp1 = x1[i] + j, tmp2 = x2[i] + j; if ( 0 <= tmp1 && tmp1 < W ) { xs.PB( tmp1 ); } if ( 0 <= tmp2 && tmp2 < W ) { xs.PB( tmp2 ); } } } // 重複要素を消す sort( ALL( xs ) ); xs.erase( unique( ALL( xs ) ), xs.end() ); REP( i, 0, N ) { // 新しい座標の取得 x1[i] = lower_bound( ALL( xs ), x1[i] ) - xs.begin(); x2[i] = lower_bound( ALL( xs ), x2[i] ) - xs.begin(); } return xs.size(); } // 矩形範囲を 1 で埋める void paint( VVI &board, int x1, int y1, int x2, int y2 ) { REP( i, y1, y2 ) { REP( j, x1, x2 ) { board[i][j] = 1; } } return; } // BFS で塗り潰し void bfs( VVI &board, int y, int x ) { const int H = board.size(), W = board[0].size(); queue< PII > que; que.push( MP( y, x ) ); while ( !que.empty() ) { auto cur = que.front(); que.pop(); if ( board[ cur.fst ][ cur.snd ] ) { continue; } board[ cur.fst ][ cur.snd ] = 1; REP( d, 0, 4 ) { auto next = cur; next.fst += dir[d][0]; next.snd += dir[d][1]; if ( !( 0 <= next.fst && next.fst < H && 0 <= next.snd && next.snd < W ) ) { continue; } que.push( next ); } } return; } int main() { cin.tie( 0 ); ios::sync_with_stdio( false ); while ( true ) { int w, h; cin >> w >> h; if ( !( w | h ) ) { break; } int n; cin >> n; VI x1( n ), y1( n ), x2( n ), y2( n ); REP( i, 0, n ) { cin >> x1[i] >> y1[i] >> x2[i] >> y2[i]; } const int W = comp( x1, x2, w ), H = comp( y1, y2, h ); VVI board( H, VI( W, 0 ) ); REP( i, 0, n ) { paint( board, x1[i], y1[i], x2[i], y2[i] ); } int res = 0; REP( i, 0, H ) { REP( j, 0, W ) { if ( board[i][j] ) { continue; } res++; bfs( board, i, j ); } } cout << res << endl; } return 0; }