fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long
  4. const int maxN = 510;
  5. int grid[maxN][maxN];
  6. int visited[maxN][maxN];
  7. int dx[4] = {-1, 0, 0, 1};
  8. int dy[4] = {0, 1, -1, 0};
  9.  
  10. bool valid(int x, int y, int m, int n) {
  11.     return x >= 0 && x < m && y >= 0 && y < n;
  12. }
  13.  
  14. int main() {
  15.     ios::sync_with_stdio(false);
  16.     cin.tie(nullptr);
  17.  
  18.     int m, n, Q;
  19.     cin >> m >> n >> Q;
  20.     int start_x = -1, start_y = -1;
  21.     for(int i = 0; i < m; i++){
  22.         for(int j = 0; j < n; j++){
  23.             cin >> grid[i][j];
  24.             if(grid[i][j] == -2){
  25.                 start_x = i;
  26.                 start_y = j;
  27.             }
  28.         }
  29.     }
  30.  
  31.     int l = 1, r = 2000, answer = r;
  32.     while(l <= r){
  33.         int mid = (l + r) / 2;
  34.  
  35.         // 1) 正確重置 visited
  36.         for(int i = 0; i < m; i++){
  37.             for(int j = 0; j < n; j++){
  38.                 visited[i][j] = 0;
  39.             }
  40.         }
  41.  
  42.         // 2) BFS，半徑用 mid
  43.         queue< pair<pair<int,int>,int> > q;
  44.         visited[start_x][start_y] = 1;       // 標記起點
  45.         q.push({{start_x, start_y}, mid});
  46.  
  47.         while(!q.empty()){
  48.             auto cur = q.front(); q.pop();
  49.             int x = cur.first.first;
  50.             int y = cur.first.second;
  51.             int t = cur.second;
  52.             if(t == 0) continue;
  53.  
  54.             for(int d = 0; d < 4; d++){
  55.                 int nx = x + dx[d];
  56.                 int ny = y + dy[d];
  57.                 if(!valid(nx, ny, m, n)) continue;
  58.                 if(grid[nx][ny] == -1) continue;  // 岩石跳過
  59.                 if(visited[nx][ny]) continue;     // 已訪跳過
  60.  
  61.                 visited[nx][ny] = 1;
  62.                 if(grid[nx][ny] > 0) {
  63.                     // 遇到新炸彈，重置剩餘半徑
  64.                     q.push({{nx, ny}, grid[nx][ny]});
  65.                 } else {
  66.                     // 一般推進
  67.                     q.push({{nx, ny}, t - 1});
  68.                 }
  69.             }
  70.         }
  71.  
  72.         // 3) 統計被引爆格數
  73.         int sum = 0;
  74.         for(int i = 0; i < m; i++){
  75.             for(int j = 0; j < n; j++){
  76.                 if(visited[i][j]) sum++;
  77.             }
  78.         }
  79.  
  80.         // 4) 二分條件：至少引爆 Q 格
  81.         if(sum >= Q){
  82.             answer = mid;
  83.             r = mid - 1;
  84.         } else {
  85.             l = mid + 1;
  86.         }
  87.     }
  88.  
  89.     cout << answer << "\n";
  90.     return 0;
  91. }
  92.  
Success #stdin #stdout 0.01s 5288KB
comments (?)
stdin
copy 
4 6 10
0 0 -1 -1 -1 0
0 0 -1 1 -1 2
0 -1 0 -1 0 0
2 -2 0 0 0 -1
stdout
copy 
5
https://ideone.com/gfDm4w
language:
C++14 (gcc 8.3)
created:
1 day ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!