g276 - 2. 魔王迷宮
題目描述
題目描述了一個在 n x m 棋盤上移動的魔王模擬問題。每個魔王有初始位置和移動向量。魔王移動前會在當前位置放置炸彈，如果移動到有炸彈的位置，炸彈和魔王都會消失。題目要求計算當所有魔王都消失後，棋盤上剩餘的炸彈數量。
解題思路
此題的核心是模擬魔王的移動和炸彈的放置與引爆過程。使用一個二維陣列 boom 來記錄每個位置是否有炸彈。對於每個回合，首先遍歷所有存活的魔王，在它們的位置放置炸彈。然後，移動每個魔王，並檢查是否超出邊界或移動到有炸彈的位置。如果超出邊界或移動到有炸彈的位置，則將魔王標記為死亡，並將炸彈引爆（將 boom 陣列中的值設為 0）。最後，統計 boom 陣列中剩餘的炸彈數量。
複雜度分析
- 時間複雜度: O(n * m * q) 其中 n 和 m 是棋盤大小，q 是魔王的數量。最壞情況下，需要模擬多個回合，並且在每個回合中遍歷整個棋盤和所有魔王。
- 空間複雜度: O(n * m) 主要用於儲存
boom陣列，記錄每個位置是否有炸彈。
程式碼
#include <iostream>
using namespace std;
struct boss{
int x,y,xv,yv;
bool live;
};
boss boss[505];
int boom[105][105],next[105][105],n,m,q,t;
int main(){
cin.tie(0); ios::sync_with_stdio(false);
cin >> n >> m >> q;
t=q;
for(int i=0;i<q;++i){
cin >> boss[i].x >> boss[i].y >> boss[i].xv >> boss[i].yv;
boss[i].live=1;
}
while(t>0){
for(int i=0;i<q;++i){
if(boss[i].live){
boom[boss[i].x][boss[i].y]=1;
}
}
for(int i=0;i<q;++i){
if(boss[i].live){
boss[i].x+=boss[i].xv;
boss[i].y+=boss[i].yv;
if(boss[i].x>=n||boss[i].y>=m||boss[i].x<0||boss[i].y<0){
boss[i].live=0;
--t;
}
else if(boom[boss[i].x][boss[i].y]){
boom[boss[i].x][boss[i].y]=-1;
boss[i].live=0;
--t;
}
}
}
for(int i=0;i<n;++i){
for(int j=0;j<m;++j){
if(boom[i][j]==-1)boom[i][j]=0;
}
}
}
for(int i=0;i<n;++i){
for(int j=0;j<m;++j){
t+=boom[i][j];
}
}
cout << t;
}