#34183: C++解題思路,是"同時"移動而非"逐一"


kk20180820@gmail.com (Wayne Yang)

學校 : 國立鳳山高級中學
編號 : 172018
來源 : [49.159.254.231]
最後登入時間 :
2024-03-16 17:31:07
g276. 2. 魔王迷宮 -- 2021年9月APCS | From: [49.159.254.231] | 發表日期 : 2023-03-04 01:06

/*

    bool b[105][105] = {};               //建立一布林陣列紀錄回合結束時所有在場的炸彈的位置,

                                                     //該陣列在所有魔王走的走完,S的S完時,掃描d[ ][ ]進行紀錄,並將被引爆的炸彈掃除(掃描c[ ][ ])


    bool c[105][105] = {};               //紀錄該回合中被魔王踩到而引爆的炸彈的位置,最後在被b[ ][ ]記錄完後該格初始化
    bool d[105][105] = {};              //紀錄該回合中魔王有放置炸彈的位置,進行紀錄的先決條件是該魔王並未被炸S

整個炸彈記錄流程算是該題的核心了,不枉費花3個布林陣列進行紀錄,最重要的是魔王的移動

並不像for迴圈是一個一個進行的,該題意境是 " 同時間 "

 

首先,魔王是否被炸S,是在魔王下一回合起步前進行檢查的

如果沒被炸S,就放置炸彈,d[ ][ ]設定為true,不直接更動b[ ][ ]是因為會被下一位跑for迴圈的魔王誤踩到

既然沒S,就進行移動,這時候先不進行檢查是否引爆炸彈

----------

如果被炸S了,就不會放置炸彈,並且在c[ ][ ]設定為true,表示回合結束時該格炸彈清除,

不直接更動b[ ][ ]是因為下一位跑for迴圈的魔王會踩不到,一定要讓他踩到,這是天命

 

回合結束,b[ ][ ]對有被踩到的炸彈進行清除(c[ ][ ]),對新放置的炸彈進行紀錄(d[ ][ ])

c[ ][ ]和d[ ][ ]進行初始化

繼續下一回合~~

*/

 

 

#include<iostream>
using namespace std;

int main(void)
{
    short n,m,k;                               //short是範圍更小的整數,int吃4位元組,short吃2位元組,小小節省空間
    cin>>n>>m>>k;                      //輸入第一行的三個整數

    bool b[105][105] = {};               //建立一布林陣列紀錄回合結束時所有在場的炸彈的位置,

                                                     //該陣列在所有魔王走的走完,S的S完時,掃描d[ ][ ]進行紀錄,並將被引爆的炸彈掃除(掃描c[ ][ ])


    bool c[105][105] = {};               //紀錄該回合中被魔王踩到而引爆的炸彈的位置,最後在被b[ ][ ]記錄完後該格初始化
    bool d[105][105] = {};              //紀錄該回合中魔王有放置炸彈的位置,進行紀錄的先決條件是該魔王並未被炸S

                                                    //在被b[ ][ ]記錄完後初始化


    int a[505][5]={};                       //魔王的狀態陣列(a[ ][0] : 起步前的x位置,a[ ][1] : 起步前的y位置,a[ ][2] : 每一回合移動的x步數

                                                    //,a[ ][3] : 每一回合移動的y步數,a[ ][4] : 魔王是否活著(1活0死)   )

    for(short r=0;r<k;r++)             //輸入題目有給予的魔王前四個狀態,並將魔王的a[ ][4]設為1表示活著
    {
        cin>>a[r][0]>>a[r][1]>>a[r][2]>>a[r][3];
        a[r][4] = 1;
    }

    short ks = k;                            //ks紀錄魔王數量

    while(ks>0)                             //在魔王數量小於0時終止該迴圈
    {
        for(short r=0;r<k;r++)
        {


            if(a[r][4] == 1)                //檢查該編號魔王是否活著
            {
                if( ! b[ a[r][0] ][ a[r][1] ])   //若是活著,檢查魔王踩到的那一格有沒有炸彈(全場炸彈紀錄b[ ][ ])
                {
                    d[ a[r][0] ][ a[r][1] ] = true;   //放置炸彈(d[ ][ ])
                    a[r][0] += a[r][2];                 //進行移動
                    a[r][1] += a[r][3];

                }else{
                    c[ a[r][0] ][ a[r][1] ] = true;  //如果有炸彈,就做記號(c[ ][ ]),回合結束時清掉該格炸彈
                    a[r][4] = 0;                          //魔王判定已S
                    ks--;                                    //少一位魔王
                }

                if(a[r][0]>=n || a[r][0]<0 ||       //魔王如果走出邊界,也判定已S,並且少一位魔王
                    a[r][1]>=m || a[r][1]<0)
                {
                    a[r][4] = 0;
                    ks--;
                }


            }
        }

        for(short i=0;i<n;i++)                    //進行逐格掃描
        {
            for(short j=0;j<m;j++)
            {
                if(d[i][j])
                {
                    b[i][j] = true;                    //d[ ][ ] 記錄到b[ ][ ]
                    d[i][j] = false;
                }
                
                if(c[i][j])
                {
                    b[i][j] = false;                  //c[ ][ ]記錄到b[ ][ ]
                    c[i][j] = false;
                }
            }
        }

 

    }

    int ans=0;                                     //最後等到魔王S光,對b[ ][ ]進行逐格掃描,檢查有幾 "格" 炸彈留在場上,

                                                         //剛剛有看到其他作者的解題報告,題目有進行修正了

    for(short i=0;i<n;i++)
    {
        for(short j=0;j<m;j++)
        {
            if(b[i][j])
            {
                ans++;
            }
        }
    }

    cout<<ans;                                  //印出答案

    return 0;                                      //高中電腦老師教導return 0;可以友善電腦 ouob
}

 

//以上結束~~\(ouo)/

 
ZeroJudge Forum