BNUOJ 1038 Flowers：BFS 統計多邊形內部格子數

問題描述

M x N（≤100）字符網格，'*' 為多邊形邊界，'.' 為空格。只能在邊界**內部**的空格種花。內部定義：從該點出發，向上下左右四方向移動，**最終都會遇到邊界**（即無法走出邊界到達網格外）。求內部空格總數。

解法：反向 BFS 從外部標記

• 從網格四邊的 '.' 發起 BFS，標記所有能到達邊界外的空格為「外部」。
• 剩餘未標記的 '.' 即為內部格子。
• 或直接對每個未訪問 '.' 做 BFS，若 BFS 過程中觸及網格邊緣（坐標越界），則該連通塊為外部，計數 0；否則為內部，計數該連通塊大小。

代碼（第二種做法）

int bfs(int x, int y) {
    queue q; q.push({x,y});
    vis[x][y]=1; int cnt=1, flag=1;
    while(!q.empty()) {
        auto cur = q.front(); q.pop();
        for(int d=0;d<4;d++) {
            int nx=cur.x+dx[d], ny=cur.y+dy[d];
            if(nx<0||nx>=n||ny<0||ny>=m) { flag=0; continue; }
            if(!vis[nx][ny] && grid[nx][ny]=='.') {
                vis[nx][ny]=1; cnt++; q.push({nx,ny});
            }
        }
    }
    return flag ? cnt : 0;
}
int main() {
    while(scanf("%d%d",&n,&m)>0) {
        for(int i=0;i