想法

從題目中可以看出，只要半徑越長，可以得到的炸彈數量肯定越多，所以答案顯然呈現單調排列，可以直接對答案作二分搜，所以解題方法就是先對答案作二分搜，然後在每次搜尋時，使用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 ;
}

 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千的情形。

 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

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