POJ 4022 ASCII Area：DFS 求斜線圍成區域面積

問題描述

給定 h×w 字符網格，字符為 '/', '\', '.'。'/' 和 '\' 形成閉合多邊形，求所有多邊形內部面積總和。規則：

• 每個 '/' 或 '\' 貢獻 0.5 面積
• 多邊形內部的 '.' 貢獻 1 面積
• 外部 '.' 不計面積

關鍵難點：內部點識別

不能簡單用 4 方向 DFS，因為斜線形成的邊界允許「斜向連通」。例如：

/ .
. \

中心區域是內部，但 4 方向無法從一個內部點走到另一個。

解法：8 方向 DFS + 邊界穿越檢測

1. 對每個未訪問的 '.' 啟動 DFS
2. 8 方向擴展（4 直向 + 4 斜向）
3. 斜向移動時，檢查是否「穿越」了斜線邊界
4. 若 DFS 觸及邊界 → 該連通塊為外部，面積 = 0
5. 否則累加內部點數 + 邊界斜線數/2

斜向穿越判斷邏輯

從 (x,y) 移動到 (nx,ny) (|dx|=|dy|=1) 時，檢查中間兩個相鄰格子：

• 左上→右下：檢查 (x,y+1) 是否為 '/' 或 (x+1,y) 是否為 '\'
• 右上→左下：檢查 (x,y) 是否為 '/' 或 (x+1,y+1) 是否為 '\'
• 若有斜線阻擋 → 不可通過

完整代碼

#include 
#include 
using namespace std;

const int MAXN = 128;
char g[MAXN][MAXN];
int vis[MAXN][MAXN];
int h, w, ans;

int dx[4] = {0,0,-1,1}, dy[4] = {1,-1,0,0};
int ddx[4] = {-1,1,1,-1}, ddy[4] = {1,-1,1,-1};

int dfs(int x, int y) {
    vis[x][y] = 1;
    int area = 1;  // 當前點貢獻 1
    
    // 4 直向
    for (int k = 0; k < 4; ++k) {
        int nx = x + dx[k], ny = y + dy[k];
        if (nx < 0 || nx >= h || ny < 0 || ny >= w) return -1;  // 觸及邊界 = 外部
        if (g[nx][ny] == '.' && vis[nx][ny] == -1) {
            int sub = dfs(nx, ny);
            if (sub == -1) return -1;
            area += sub;
        }
    }
    
    // 4 斜向
    for (int k = 0; k < 4; ++k) {
        int nx = x + ddx[k], ny = y + ddy[k];
        if (nx < 0 || nx >= h || ny < 0 || ny >= w) return -1;
        
        // 穿越檢測
        int minx = min(x, nx), maxx = max(x, nx);
        int miny = min(y, ny), maxy = max(y, ny);
        if ((minx == nx && miny == ny) || (minx == x && miny == y)) {  // 左上→右下
            if (g[minx][miny+1] == '/') continue;
        }
        if ((minx == nx && maxy == ny) || (minx == x && maxy == y)) {  // 右上→左下
            if (g[minx][miny] == '\\') continue;
        }
        
        if (g[nx][ny] == '.' && vis[nx][ny] == -1) {
            int sub = dfs(nx, ny);
            if (sub == -1) return -1;
            area += sub;
        }
    }
    return area;
}

int main() {
    scanf("%d%d", &h, &w);
    for (int i = 0; i < h; ++i) scanf("%s", g[i]);
    
    memset(vis, -1, sizeof(vis));
    ans = 0;
    for (int i = 0; i < h; ++i)
        for (int j = 0; j < w; ++j)
            if (g[i][j] == '.' && vis[i][j] == -1)
                ans = max(ans, dfs(i, j));
    
    // 加上斜線貢獻：每個 '/' 或 '\' 算 0.5
    int slash = 0;
    for (int i = 0; i < h; ++i)
        for (int j = 0; j < w; ++j)
            if (g[i][j] == '/' || g[i][j] == '\\') ++slash;
    
    printf("%.1f\n", ans + slash * 0.5);
    return 0;
}

關鍵細節

• 訪問標記 -1/1：-1 未訪問，1 正在訪問/已訪問
• 返回 -1 傳播外部標記：任一路徑觸及邊界，整個連通塊作廢
• 面積計算分離：DFS 只算內部 '.' 數，斜線單獨統計 ×0.5
• 取最大值：題目可能有多個閉合區域，取最大面積（樣例暗示）