CSAcademy 25. Zone Capture ( BCC )
題意:
給一個 01 矩陣 A[ N ][ M ]。你可以選擇一個 0 轉為 1,轉換後,所有不和任意一個邊界的 0 屬於同一個連通塊 ( 上下左右,且兩者皆 0 視為相鄰 ) 的所有 0 都會轉為 1。問最多可以有多少 1。
制約:
1 ≤ N, M ≤ 1000
解法:
將所有格子化為節點編號,令 0 表示邊界, 將屬於邊界的 '0' 的節點連到 0。接著將所有相鄰的 '0' 也連一條邊。找出所有割點後,將 0 = 邊界 屬於的那塊 bcc 全部記為已拜訪。答案是原本的黑色格子數 + max( 1, 最大的剩餘連通塊大小 )。
時間 / 空間複雜度:
O( N * M )
#include <bits/stdc++.h> using namespace std; const int dx[] = { 1, 0, -1, 0 }; const int dy[] = { 0, 1, 0, -1 }; const int MAXN = 1000; const int MAXM = 1000; int N, M; int mat[ MAXN ][ MAXM ]; vector< int > G[ MAXN * MAXM + 1 ]; // 0 preserved for "border" int tin[ MAXN * MAXM + 1 ]; int low[ MAXN * MAXM + 1 ]; bool is_cut[ MAXN * MAXM + 1 ]; void dfs_bcc( int u, int fa ) { static int clk = 0; low[ u ] = tin[ u ] = ++clk; for( int v : G[ u ] ) { if( v == fa ) continue; if( not tin[ v ] ) { dfs_bcc( v, u ); if( low[ v ] >= tin[ u ] and u != 0 ) { is_cut[ u ] = true; } low[ u ] = min( low[ u ], low[ v ] ); } low[ u ] = min( low[ u ], tin[ v ] ); } } signed main() { ios::sync_with_stdio( 0 ); cin >> N >> M; int original_black = 0; for( int i = 0; i < N; ++i ) { for( int j = 0; j < M; ++j ) { cin >> mat[ i ][ j ]; original_black += mat[ i ][ j ]; } } for( int i = 0; i < N; ++i ) { for( int j = 0; j < M; ++j ) { if( mat[ i ][ j ] ) continue; if( i == 0 or i + 1 == N or j == 0 or j + 1 == M ) { G[ i * M + j + 1 ].emplace_back( 0 ); G[ 0 ].emplace_back( i * M + j + 1 ); } for( int di = 0; di < 4; ++di ) { int nx = i + dx[ di ]; int ny = j + dy[ di ]; if( not ( 0 <= nx and nx < N and 0 <= ny and ny < M ) ) continue; if( mat[ nx ][ ny ] ) continue; G[ i * M + j + 1 ].emplace_back( nx * M + ny + 1 ); G[ nx * M + ny + 1 ].emplace_back( i * M + j + 1 ); } } } dfs_bcc( 0, -1 ); int max_cc_size = 0; { static bool vis[ MAXN * MAXM + 1 ]; vis[ 0 ] = true; queue< int > que; que.emplace( 0 ); while( not que.empty() ) { int u = que.front(); que.pop(); for( int v : G[ u ] ) { if( is_cut[ v ] ) continue; if( vis[ v ] ) continue; vis[ v ] = true; que.emplace( v ); } } for( int i = 0; i < N; ++i ) { for( int j = 0; j < M; ++j ) { if( mat[ i ][ j ] ) continue; if( vis[ i * M + j + 1 ] ) continue; vis[ i * M + j + 1 ] = true; int cnt = 1; que.emplace( i * M + j + 1 ); while( not que.empty() ) { int u = que.front(); que.pop(); for( int v : G[ u ] ) { if( vis[ v ] ) continue; vis[ v ] = true; ++cnt; que.emplace( v ); } } max_cc_size = max( max_cc_size, cnt ); } } } cout << original_black + max( 1, max_cc_size ) << endl; return 0; }