您现在的位置：程式碼之家 >> 編程語言 > >> C語言 >> C++ >> 關於C++

CSU 1569 Wet Tiles：BFS 多源擴散模擬漏水面積計算

編輯：關於C++

問題描述

X×Y 地磚網格 (≤1000×1000)，L 個漏水源，T 分鐘後到達。水每分鐘向 4 方向擴散一格。W 條內牆阻擋 (端點座標給定，軸平行或 45°)。求 T 分鐘後濕磚總數。

核心建模：分層 BFS (波前擴散)

多源 BFS：所有漏水源同時入隊，時刻 0
每分鐘處理完當前層所有節點，再進入下一層
牆壁預處理：標記 `wall[x][y] = true`
T 分鐘後停止，統計已訪問格子數

牆壁處理關鍵：離散化線段標記

牆端點 (x1,y1)-(x2,y2)，三種情況：

水平：y1==y2，x 從 min 到 max 標記
垂直：x1==x2，y 從 min 到 max 標記
對角：|dx|==|dy|，x,y 同步增減標記

完整代碼


#include 
#include 
#include 
using namespace std;

const int MAXN = 1005;
struct Pos { int x, y; };
int grid[MAXN][MAXN];  // 0=乾, 1=濕, 2=牆
int X, Y, T, L, W;
Pos leaks[105];
int dx[4] = {0,0,1,-1}, dy[4] = {1,-1,0,0};
queue q[2];  // 雙隊列交替實現分層

void bfsLayer(int cur) {
    while (!q[cur].empty()) {
        Pos p = q[cur].front(); q[cur].pop();
        for (int d = 0; d < 4; ++d) {
            int nx = p.x + dx[d], ny = p.y + dy[d];
            if (nx > 0 && nx <= X && ny > 0 && ny <= Y && grid[nx][ny] == 0) {
                grid[nx][ny] = 1;
                q[!cur].push({nx, ny});
            }
        }
    }
}

int main() {
    while (scanf("%d", &X) == 1 && X != -1) {
        scanf("%d%d%d%d", &Y, &T, &L, &W);
        memset(grid, 0, sizeof(grid));
        while (!q[0].empty()) q[0].pop();
        while (!q[1].empty()) q[1].pop();
        
        for (int i = 0; i < L; ++i) {
            scanf("%d%d", &leaks[i].x, &leaks[i].y);
            grid[leaks[i].x][leaks[i].y] = 1;
            q[0].push(leaks[i]);
        }
        
        for (int i = 0; i < W; ++i) {
            int x1, y1, x2, y2;
            scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
            // 統一方向：x1<=x2, 同 x 時 y1<=y2
            if (x1 > x2 || (x1==x2 && y1 > y2)) {
                swap(x1, x2); swap(y1, y2);
            }
            if (x1 == x2) {  // 垂直
                for (int y = y1; y <= y2; ++y) grid[x1][y] = 2;
            } else if (y1 == y2) {  // 水平
                for (int x = x1; x <= x2; ++x) grid[x][y1] = 2;
            } else if (x2 - x1 == y2 - y1) {  // 主對角線
                for (int x = x1, y = y1; x <= x2; ++x, ++y) grid[x][y] = 2;
            } else {  // 副對角線
                for (int x = x1, y = y2; x <= x2; ++x, --y) grid[x][y] = 2;
            }
        }
        
        int cur = 0;
        while (T-- > 0 && !q[cur].empty()) {
            bfsLayer(cur);
            cur = !cur;
        }
        
        int ans = 0;
        for (int i = 1; i <= X; ++i)
            for (int j = 1; j <= Y; ++j)
                if (grid[i][j] == 1) ++ans;
        printf("%d\n", ans);
    }
    return 0;
}