【題解】ZeroJudge g596: 2. 動線安排

【題目敘述】https://zerojudge.tw/ShowProblem?problemid=g596
【解題想法】模擬

#include <iostream>
#include <map>
using namespace std;
bool myDebug = false;
const int maxn = 105;
int a[maxn][maxn]; //紀錄有幾條線經過(-1/0/1/2),-1表示有木樁
int m, n, h;
int dx[] = {-1, 1, 0, 0}; // 上(0)下(1)左(2)右(3)
int dy[] = {0, 0, -1, 1}; // 上(0)下(1)左(2)右(3)

void myPrint() {
    map <int, char> mp;
    mp[-1] = '@';
    mp[0] = '_';
    mp[1] = '*';
    mp[2] = '+';
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            cout << mp[a[i][j]];
        }
        cout << "\n";
    }
    cout << "\n";
}

int main() {
    cin >> m >> n >> h;
    int r, c, t;
    int ans = 0; //最後有線和有木樁佔據空間的面積
    int mx = 0; //操作過程中有線和有木樁佔據空間的面積最大值
    if (myDebug) myPrint();
    for (int k = 0; k < h; k++) {
        cin >> r >> c >> t;
        //有線經過則先將那些線拆掉
        for (int i = 0; i < 4; i++) {
            int nx = r + dx[i];
            int ny = c + dy[i];
            bool find = false;
            while (nx >= 0 && nx < m && ny >=0 && ny < n) {
                if (a[nx][ny] == 0) {
                    //沒有線經過
                    break;
                }
                
                if (a[nx][ny] == -1) {
                    //確定有端點木樁,才不會誤拆了屬於別的木樁的線
                    find = true;
                    break;
                }
                
                nx += dx[i];
                ny += dy[i];
            }
            if (find) {
                for (int j = min(r, nx)+1; j < max(r, nx); j++) {
                    a[j][ny]--;
                }
                for (int j = min(c, ny)+1; j < max(c, ny); j++) {
                    a[nx][j]--;
                }
            }
        }
        
        if (t == 0) {
            //加一木樁,然後連線
            a[r][c] = -1;
            for (int i = 0; i < 4; i++) {
                int nx = r + dx[i];
                int ny = c + dy[i];
                bool find = false;
                while (nx >= 0 && nx < m && ny >=0 && ny < n) {
                    if (a[nx][ny] == -1) {
                        find = true;
                        break;
                    }
                    nx += dx[i];
                    ny += dy[i];
                }
                if (find) {
                    for (int j = min(r, nx)+1; j < max(r, nx); j++) {
                        a[j][ny]++;
                    }
                    for (int j = min(c, ny)+1; j < max(c, ny); j++) {
                        a[nx][j]++;
                    }
                }
            }
        } else {
            //移除木樁
            a[r][c] = 0;
        }
        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);
        if (myDebug) myPrint();
    }
    cout << mx << "\n" << ans << "\n";
    return 0;
}

分享本文 Share with friends