Alice is playing another game called BOOM. The game has a rectangular map of size N ×M. Each 1×1 cell is a wall, an enemy, or an empty cell. In this game, a bomb has a horizontal explosion range with radius V . In other words, if the bomb is placed at cell (i, j), its explosion range is from the cell (i, j − V ) to the cell (i, j + V ). It is not allowed to place bombs at the wall cells, it is allowed to place bombs in the remaining cells. The bomb explodes at its placed cell and spreads to both horizontal sides, until it reaches the end of its explosion range or encounters a wall. Note that the wall will not be destroyed by bombs. In this game, Alice will carry exactly K bombs. Therefore, before entering the map, Alice must buy K bombs with an explosion range of V . To save in-game money, Alice will buy exactly K bombs with the minimum V but can still destroy all enemies in the map. Please help Alice to calculate the minimum V . Input The first line contains three positive integers N, M, K safety N × M, K ≤ 10^5 In the next N lines, each line contains M characters of the following characters: ’#’ is a wall, ’.’ is an empty cell, ’x’ is an enemy. Output Output the minimum V so that Alice can place K bombs to destroy all enemies. If there is no answer, output −1. Example1: input: 4 6 5
..#.xx x....x output: 1 Example 2: Input: 2 3 10 xxx xxx Output: 0 Example 3: Input: 2 2 1 x. x. Output: -1 Test case 1: With V = 1, she can place 5 bombs in cells: (1, 2),(2, 4),(3, 5),(4, 1),(4, 6). This is the minimum V . Test case 2: She can place bombs in all cells in the map. Test case 3: She cannot destroy all enemies with 1 bomb
C++
Dưới đây là một giải pháp tiềm năng để giúp Alice trong trò chơi BOOM sử dụng C++. Giải pháp này dựa trên việc sắp xếp các vị trí của kẻ thù dựa trên khoảng cách từ kẻ thù đến vách ngăn gần nhất và sau đó sử dụng chúng để tìm ra bán kính tối thiểu của quả bom cần thiết để tiêu diệt tất cả kẻ thù.
Lưu ý rằng, đây chỉ là một giải pháp tiềm năng và có thể yêu cầu một số chỉnh sửa để phù hợp với yêu cầu và dữ liệu đầu vào cụ thể của công việc.
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int MAX = 1e5;
int n, m, k, dx[MAX+5], dy[MAX+5], r[MAX+5];
char s[333][333];
typedef pair<int,int> ii; vector<ii> v;
#define x first
#define y second
bool ok(int mid){
memset(dx,0,sizeof(dx));
memset(dy,0,sizeof(dy));
for(int i = mid+1; i <=v.size(); i++){
int fi = v[i-1].x, fj = v[i-1].y;
dx[fj+1] = max(dx[fj+1],fi + mid);
dy[fj] = max(dy[fj],fi + mid);
}
for(int i=1; i<=m+1; i++){
dx[i] = max(dx[i-1],dx[i]);
dy[i] = max(dy[i-1],dy[i]);
}
for(int i=1; i<=n; i++)
if(max(dx[i],dy[n-i+1]) <=i) return 1;
return 0;
}
int main(){
ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
cin >> n >> m;
memset(s, '#', sizeof(s));
for(int i=1; i<=n; i++){
for(int j=1; j<=m; j++){
cin >> s[i][j];
if(s[i][j] == 'x') v.push_back(ii(i,j));
}
}
sort(v.begin(), v.end(), [&](ii i, ii j){
return max(i.x, max(i.y, max(n - i.x + 1, m - i.y + 1)))
< max(j.x, max(j.y, max(n - j.x + 1, m - j.y + 1)));
});
int l = 0, r = n + m, res = -1;
while(l <= r){
int mid = (l + r) >> 1;
if(ok(mid)){
res = mid;
r = mid - 1;
}else l = mid + 1;
}
cout << res;
return 0;
}Đừng quên hỏi thêm nếu bạn có bất kỳ câu hỏi nào khác và hãy thăm trituenhantao.io để nắm bắt nhiều thông tin hữu ích hơn về AI và công nghệ cùng những bài viết sâu bằng tiếng Việt! Gặp lại bạn vào lần sau nhé!