IOI'94 The Castle ( BFS )

PEG Judge - IOI '94 - The Castle
強行枚舉每個牆壁破壞後的樣子，直接把牆壁減掉，然後檢查完再加回來就行了。雖然很明顯，但要記得意識到只有破壞牆壁的連通分量會有面積的更新，所以不需要每次都檢查全部。有一點小小卡到的是後來枚舉破壞牆壁的時候忘記要清空 vis陣列。

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 50 + 5;
const int MAXM = 50 + 5;

                // W, N, E, S
const int dx[] = { 0, -1, 0, 1 };
const int dy[] = { -1, 0, 1, 0 };
const char toC[] = "WNES";

int n, m;
int cell[ MAXN ][ MAXM ];

int cnt_room, max_room;
int best_rmx, best_rmy, best_cap, best_dir;
int vis[ MAXN ][ MAXM ];
int bfs(int sx, int sy){
    int room_capacity = 0;
    queue<int> que;
    que.push( sx * MAXM + sy );
    vis[ sx ][ sy ] = 1;
    while( !que.empty() ){
        int x = que.front() / MAXM;
        int y = que.front() % MAXM;
        que.pop();
        ++room_capacity;
        for(int d = 0; d < 4; ++d){
            if( ( cell[ x ][ y ] >> d ) & 1 ) continue;
            int nx = x + dx[ d ];
            int ny = y + dy[ d ];
            assert( 1 <= nx && nx <= n && 1 <= ny && ny <= m );
            if( vis[ nx ][ ny ] ) continue;
            vis[ nx ][ ny ] = 1;
            que.push( nx * MAXM + ny );
        }
    }
    return room_capacity;
}

void solve(){
    cnt_room = max_room = 0;
    for(int i = 1; i <= n; ++i)
        for(int j = 1; j <= m; ++j)
            if( !vis[ i ][ j ] ){
                ++cnt_room;
                max_room = max<int>( max_room, bfs( i, j ) );
            }
    printf("%d\n%d\n", cnt_room, max_room);

    max_room = 0;
    for(int j = 1; j <= m; ++j)
        for(int i = n; i >= 1; --i){ // west then south
            for(int d = 0; d < 4; ++d){
                if( ( cell[ i ][ j ] >> d ) & 1 ){
                    int ni = i + dx[ d ];
                    int nj = j + dy[ d ];
                    if( ni < 1 || ni > n || nj < 1 || nj > m ) continue;
                    cell[ i ][ j ] -= ( 1 << d ); // break the wall
                    
                    memset( vis, 0, sizeof(vis) );
                    int rc = bfs( i, j );
                    if( rc > max_room ){
                        max_room = rc;
                        best_rmx = i, best_rmy = j;
                        best_dir = d;
                    }

                    cell[ i ][ j ] += ( 1 << d ); // restore the wall
                }
            }
        }
    printf("%d\n", max_room);
    printf("%d %d %c\n", best_rmx, best_rmy, toC[ best_dir ]);
}

int main(){
    scanf("%d%d", &m, &n);
    for(int i = 1; i <= n; ++i)
        for(int j = 1; j <= m; ++j)
            scanf("%d", &cell[ i ][ j ]);
    solve();
    return 0;
}