#43727: 解題想法&C++答案&註解


samlin961112@gmail.com (林哲甫)

School : 新北市私立南山高級中學
ID : 220506
IP address : [123.252.121.18]
Last Login :
2024-11-21 19:33:28
o713. 3. 連鎖反應 -- 2024年10月APCS | From: [219.70.213.92] | Post Date : 2024-10-24 22:43

想法

從題目中可以看出,只要半徑越長,可以得到的炸彈數量肯定越多,所以答案顯然呈現單調排列,可以直接對答案作二分搜,所以解題方法就是先對答案作二分搜,然後在每次搜尋時,使用BFS來找出在這個答案下所得到的炸彈數量。主要的問題在於BFS內部與一般的BFS不一樣,就算曾經到過,也可以再走一次,但是要小心無窮迴圈的問題。

剪枝

所以要開一個陣列,紀錄從那一格開始向外時,所造成的最大半徑,如果目前要找的半徑小於曾經到過的半徑,顯然代表接下來再走下去也不會到新的地方,可以直接進行減枝

複雜度

時間複雜度: 二分搜是log(n*m) , BFS是n*m(正常全部遍歷一次)+k*r(k是炸彈數量,r是炸彈半徑,炸彈所造成的重複遍歷),所以總和是O(log(n*m)*(n*m+k*r))

空間複雜度: 每個陣列大小最大都是n*m,所以是O(n*m)

以下是完整程式碼

#include <bits/stdc++.h>
using namespace std;

int n, m, q;
int r, c; // 開始點
int dx[4] = {0, 1, 0, -1};
int dy[4] = {1, 0, -1, 0};

struct bomp {
    int x, y, t; // x, y為坐標,t為炸彈剩餘範圍
};

// 再長度為l的狀態下,是否符合要求
bool bfs(const vector<vector<int>> a, int l) {
    queue<bomp> qu;
    qu.push({r, c, l});
    int ans = 1;//總共爆炸數,初始1個
    vector<vector<int>> visited(n, vector<int>(m, 0));//0代表位訪問,數值代表最遠爆炸半徑,可用於剪枝,+10來避免已訪問但是半徑為0
    visited[r][c] = l+10;

    // 開始廣度優先搜索
    while (!qu.empty()) {
        bomp now = qu.front();
        qu.pop();
        if (now.t == 0) continue; // 如果爆炸半徑為0,則停止
        for (int i = 0; i < 4; ++i) {
            int nx = now.x + dx[i];
            int ny = now.y + dy[i];
            if (nx >= 0 && nx < n && ny >= 0 && ny < m && a[nx][ny] != -1) {
                int next = max(a[nx][ny], now.t - 1); // 下一步的半徑
                // 有更大的爆炸範圍
                if (visited[nx][ny]-10 < next) {
                    if (!visited[nx][ny]) ans++; // 未訪問,機1個炸彈
                    visited[nx][ny] = next+10;//修改最遠半徑
                    qu.push({nx, ny, next}); 
                }
            }
        }
    }

    return (ans >= q); 
}

int main() {
    cin >> n >> m >> q;
    vector<vector<int>> a(n, vector<int>(m));

    // 讀取網格,並找出初始炸彈的坐標
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            cin >> a[i][j];
            if (a[i][j] == -2) {
                r = i;
                c = j;
            }
        }
    }

    int l = 0, r = n * m; // 最短0,最長就是全部
    int ans = r;

    // 二分搜
    while (l <= r) {
        int mid = (l + r) / 2;
        if (bfs(a, mid)) {
            ans = mid;
            r = mid - 1;
        } else {
            l = mid + 1;
        }
    }

    cout << ans ;
}

 
#43729: Re: 解題想法&C++答案&註解


sophie19820517@gmail.com (闕河正)

School : No School
ID : 115751
IP address : [123.110.172.57]
Last Login :
2024-11-19 13:58:19
o713. 3. 連鎖反應 -- 2024年10月APCS | From: [123.240.57.165] | Post Date : 2024-10-25 16:43

 int l = 0, r = n * m; // 最短0,最長就是全部

 

可以理解為什麼最長是n*m嗎,假設一個3*3的地圖

2 2 2

2 2 2

-2 2 2

炸彈在地圖左下角,那麼最大半徑不是4就能拓展整張地圖了嗎?

半徑如果按照n*m,最大就變成9啦?

是不是我理解題目錯誤呢?

因為題目要求n,m<=500,

但答案也確實有7~8千的情形。

 
#43731: Re: 解題想法&C++答案&註解


A1eFanT (大象)

School : 國立嘉義高級中學
ID : 126073
IP address : [140.114.216.20]
Last Login :
2024-03-12 15:30:29
o713. 3. 連鎖反應 -- 2024年10月APCS | From: [140.114.217.28] | Post Date : 2024-10-25 20:04

 int l = 0, r = n * m; // 最短0,最長就是全部

 

可以理解為什麼最長是n*m嗎,假設一個3*3的地圖

2 2 2

2 2 2

-2 2 2

炸彈在地圖左下角,那麼最大半徑不是4就能拓展整張地圖了嗎?

半徑如果按照n*m,最大就變成9啦?

是不是我理解題目錯誤呢?

因為題目要求n,m<=500,

但答案也確實有7~8千的情形。

如果考慮有障礙物的情況就會需要繞路了,比如
-2 0 0 0 0

-1 -1 -1 -1 0

0 0 0 0 0 

0 -1 -1 -1 -1

0 0 0 0 0

 
#43732: Re: 解題想法&C++答案&註解


sophie19820517@gmail.com (闕河正)

School : No School
ID : 115751
IP address : [123.110.172.57]
Last Login :
2024-11-19 13:58:19
o713. 3. 連鎖反應 -- 2024年10月APCS | From: [123.240.57.165] | Post Date : 2024-10-25 20:21

原來如此,是我沒想到有繞路這件事

 
ZeroJudge Forum