2021/9/5 魔王迷宮

2023.1.26 PM 03:30 by CBJ

來源 : https://zerojudge.tw/ShowProblem?problemid=g276
出題者 : 2021年9月APCS
標籤 : 模擬法
難易度 : 2

解題想法 : 
這題的小細節非常的多，實作上需要特別注意，以下列出數個可能發生的失誤 :

失誤1 - 炸彈沒有先放
由於我們不可能達到題目中所謂的「同時移動」，所以我們必須要先放下炸彈，因為如果每個魔王按順序邊走邊放的話，可能會發生走到的點目前沒有炸彈但順序比較後面的魔王會放炸彈在這裡的情形。

失誤2 - 有魔王踩到炸彈時就把炸彈移除
還是因為一樣的原因，我們沒有辦法同時讓所有魔王移動，因此若有其中一個魔王踩到炸彈就把炸彈移除，那同回合後面的魔王踩到這個位置就不會有炸彈，因此必須要等到所有人走完才能確定要移除的點，實作上可以建一個陣列紀錄這回合要被移除的炸彈座標，等回合結束後再做移除的動作。

失誤3 - 沒判斷出界
請記得一定要判斷是否出界，否則會出現記憶體存取的錯誤。

失誤4 - 有魔王死了就把它移除
在迴圈遍歷的過程中若陣列有被移除東西，就無法讓迴圈能夠遍歷所有的內容，這絕對不是我們樂見的。解決方法是，如果堅持要用移除的方式，那就要使用失誤3所提到的解方，用個陣列存，但筆者使用的方式是開一個陣列紀錄0~k的存活情形(1表示存活，0反之)，並以此陣列的總和作為迴圈是否繼續執行的參考。

突破這四個常見的失誤後，相信是個很好實作的題目，請務必去嘗試看看。

//C++ language

#include<iostream>
#include<vector> //vector 
#include<numeric> //accumulate()
#include<tuple> //tuple
#define five tuple<int,int,int,int,int>
#define sum_of_alive accumulate(alive.begin(),alive.end(),0)
using namespace std;
int n,m,k; 
bool inrange(int x,int y){
    return x>=0 and y>=0 and x<n and y<m;
}
int main(){
    cin>>n>>m>>k;
    vector<vector<int>> bomb(n,vector<int>(m,0));
    vector<int> alive(k,1);
    vector<five>data;
    for(int i=0;i<k;i++){
        int r,c,s,t; cin>>r>>c>>s>>t;
        data.push_back({i,r,c,s,t});
    }
    while(sum_of_alive>0){
        vector<pair<int,int>> rm_bomb;
        for(five f:data){
            int i=get<0>(f),
                r=get<1>(f),
                c=get<2>(f);
            if(alive[i]) bomb[r][c]=1;
        }
        for(five f:data){
            int i=get<0>(f),
                r=get<1>(f),
                c=get<2>(f),
                s=get<3>(f),
                t=get<4>(f);
            if(alive[i]==0) continue;
            int nextr=r+s, nextc=c+t;
            data[i]={i,nextr,nextc,s,t};
            if(inrange(nextr,nextc)){
                if(bomb[nextr][nextc]){
                    alive[i]=0;
                    rm_bomb.push_back({nextr,nextc});
                }
            }
            else alive[i]=0;
        }
        for(pair<int,int>p: rm_bomb)
            bomb[p.first][p.second]=0;
    }
    int ans=0;
    for(vector<int>v:bomb){
        for(int i:v) ans+=i;
    }
    cout<<ans<<"\n";
    return 0;
}

## Python language

n,m,k=map(int,input().split())
bomb=[[0]*m for _ in range(n)]
alive=[1]*k

data=[] #[index,r,c,s,t]
for i in range(k):
    data.append([i]+[int(x) for x in input().split()])

while sum(alive)>0:
    rm_bomb=[]
    
    for i,r,c,_,_ in data:
        if alive[i]==1: bomb[r][c]=1 
        
    for i,r,c,s,t in data:
        if alive[i]==0: continue
        nextr,nextc=r+s,c+t
        data[i]=[i,nextr,nextc,s,t]
        if 0<=nextr<n and 0<=nextc<m:
            if bomb[nextr][nextc]==1:
                alive[i]=0
                rm_bomb.append([nextr,nextc])
        else:
            alive[i]=0
            
    for x,y in rm_bomb:
        bomb[x][y]=0
ans=0
for i in bomb:
    for j in i:
        ans+=j 
print(ans)

相關文章

分享此文：