g596 - 2. 動線安排
題目描述
題目描述一個 $m \times n$ 的展場，可以放置木樁並用線連接木樁，形成動線。給定 $h$ 次操作，每次操作可以在 $(r, c)$ 位置放置或移除木樁。要求在所有操作過程中，記錄並輸出有線和有木樁佔據空間的最大面積，以及所有操作完成後，有線和有木樁佔據空間的面積。
解題思路
本題的核心是模擬動線的建立和移除。使用一個二維陣列 a[m][n] 來表示展場，其中 a[i][j] 的值表示該位置是否有線或木樁。
- 當放置木樁時，向上下左右方向尋找最近的木樁並連接，連接的過程會更新
a[i][j]的值。 - 當移除木樁時，移除木樁本身以及與其相連的線。
- 在每次操作後，計算有線和有木樁佔據的空間面積，並更新最大面積。
addedge 函數用於連接兩個木樁之間的線，它會更新中間位置的 a[i][j] 值。
主函數中，遍歷所有操作，執行相應的放置或移除操作，並計算面積。
複雜度分析
- 時間複雜度: O(h * m * n)。在最壞情況下，每次操作都需要遍歷整個展場來尋找最近的木樁並連接線。
- 空間複雜度: O(m * n)。需要一個二維陣列
a[m][n]來表示展場。
程式碼
#include <iostream>
using namespace std;
int a[105][105],m,n,h,r,c,t,ans=0,mx=0;
int dx[]={-1,1,0,0},dy[]={0,0,-1,1};
void addedge(int nx,int ny,int v){
for (int j = min(r, nx)+1; j < max(r, nx); ++j)
a[j][ny]+=v;
for (int j = min(c, ny)+1; j < max(c, ny); ++j)
a[nx][j]+=v;
}
int main() {
cin >> m >> n >> h;
for (int k = 0; k < h; k++) {
cin >> r >> c >> t;
a[r][c]=(t?0:-1);
for (int i = 0; i < 4; ++i) {
int nx = r + dx[i],ny = c + dy[i];
while (nx >= 0 && nx < m && ny >=0 && ny < n && a[nx][ny]) {
if (a[nx][ny] == -1) {
addedge(nx,ny,-1);
break;
}
nx += dx[i];
ny += dy[i];
}
if (!t){
nx = r + dx[i],ny = c + dy[i];
while (nx >= 0 && nx < m && ny >=0 && ny < n) {
if (a[nx][ny] == -1) {
addedge(nx,ny,1);
break;
}
nx += dx[i];
ny += dy[i];
}
}
}
ans = 0;
for (int i = 0; i < m; i++)
for (int j = 0; j < n; j++)
ans += (a[i][j] != 0);
mx = max(mx, ans);
}
cout << mx << "\n" << ans;
}