最後編輯時間: 2024/11/05

APCS 2024/10月 實作第二題解題思路

▌前言

現在來解 APCS 2024/10月 實作第二題蒐集寶石 這題的題目
我的解法不會是最好的解法，但是是我下意識想出來的解法
因此雖然不會是最好的解法，但會是比較好理解好想出來的

▌題目

有一個 M×N 的地圖，裡面每一格的數字紀錄著寶石的數量
如果數字是 -1 代表牆壁，有一位機器人開始位於 (r,c) 的位置
且方向朝右邊，他遵循著以下規則行走。
1. 若機器人位於的格字內寶石數量為 0，則機器人程式終止。
2. 有一個分數S，將S加上當前格寶石數量，並且撿起一顆寶石
3. 若S是 k 的倍數，則向右轉 90 度。
4. 若機器人面向的格子是牆壁或是超出邊界則繼續向右轉 90 度
    直到面向的格子非牆壁或非超出邊界，並回到第 1 步
以下是範例題題目，依照上述規則所執行，執行路線如下圖

機器人一開始在 (2,1) 且 k=2，向右走兩步後分數 3+2+3=8
8 是 2(k=2) 的倍數所以右轉 90 度。再來往下走一步分數為 11
接下來需要向右轉 2 次 90 度才不會面向牆壁或是邊界外的格子
向前行走一步走到座標 (2,3)，由於在之前已經先拿走一顆寶石
因此該位置寶石數量變為 2，因此分數變為 13，再繼續往上走
兩步到 (0,3) 分數為 16， 16 為 2(k=2) 的倍數所以右轉 90 度
向前走一格到 (0,4) 後需要向右轉兩次 90 度，回到 (0,3) 後
由於寶石數量為 0，機器人停止。過程機器人總共撿了8顆寶石
所以最後的輸出答案為8，以下為程式輸入格式，還有兩題測資

▌想法

其實個程式也沒到太難，只要熟悉陣列用法基本上就寫得出來
首先了解結束條件是當前格寶石為0，因此加重複直到那格為0
之後我想到行走有4種可能，變數設jd(角度)很人性化對吧qwq
jd使用0、1、2、3來代表90、0、270、180的角度
所以jd等於0時往右移動，即陣列(此設定為mn，還好不是nm)
mn[r][c]的c增加1，其他角度以此類推，r+1、c-1、r-1
加減之後開始判斷當前位置是否屬於-1或者已經跑到陣列外面
如果成立，那就回來，轉彎後繼續行走，重複直到可以正常走
大致上加上k倍數轉彎跟紀錄走過幾格程式就可以被寫出來了

▌整個程式

				
					#include <stdio.h>
int jdd(int jd){
    jd = jd + 1;
    if(jd == 4){
        jd = 0;
    }
    return(jd);
}
int main(void) {
    int m,n,k,r,c,i,j,jd,qwq=0,b=0,no=0,awa=0;
    scanf("%d%d%d%d%d",&m,&n,&k,&r,&c);
    int mn[m][n];
    for(i=0;i<m;i++){
        for(j=0;j<n;j++){
            scanf("%d",&mn[i][j]);
        }
    }
    while (mn[r][c] != 0){
        b++;
        qwq = qwq + mn[r][c];
        mn[r][c]=mn[r][c]-1;
        if(qwq%k==0){
            jd = jdd(jd);
        }
        do{
            awa=0;
            if(jd==0){
                c++;
                if (c>n-1||mn[r][c]==-1){
                    c--;
                    awa=1;
                }
            }
            if(jd==1){
                r++;
                if (r>m-1||mn[r][c]==-1){
                    r--;
                    awa=1;
                }
            }
            if(jd==2){
                c--;
                if (c<0||mn[r][c]==-1){
                    c++;
                    awa=1;
                }
            }
            if(jd==3){
                r--;
                if (r<0||mn[r][c]==-1){
                    r++;
                    awa=1;
                }
            }
            if(awa==1){
                jd = jdd(jd);
            }
        }while(awa!=0);
    }
    printf("%d",b);
}

▌程式講解

首先已知程式結束條件為當前nm[r][c]=0，所以加上一個迴圈
如下圖這樣寫，即可完成當nm[r][c]=0之後停止該程式的功能

				
					while (mn[r][c] != 0){
}

之後呢在迴圈內先記錄所需紀錄S值，我這邊使用qwq來代表S
首先qwq加上之前跟當前格的數量，之後判斷是否是k的倍數
是的話轉彎，jd+1，然後當前那格寶石-1

				
					b++;
qwq = qwq + mn[r][c];
mn[r][c]=mn[r][c]-1;
if(qwq%k==0){
    jd = jdd(jd);
}

接下來就是行走的程式，整體也不難，就是IF疊疊樂而已
首先用do-while，確保迴圈程式必定執行一次，之後初始awa
awa是紀錄是否有出現到不能行走為位置，牆壁或著地圖邊界
之後就一路IF下去，當等於0，c+1向右走一格，以此類推
每個IF都增加個IF，判斷是否在牆壁或地圖邊界，在的話退回
就這樣一直執行，到後面偵測awa是否變1，是的話代表要轉彎
執行jd+1，然後因為轉彎了，所以在執行一次，直到前進為止

				
					do{
    awa=0;
    if(jd==0){
        c++;
        if (c>n-1||mn[r][c]==-1){
            c--;
            awa=1;
        }
    }
    if(jd==1){
        r++;
        if (r>m-1||mn[r][c]==-1){
            r--;
            awa=1;
        }
    }
    if(jd==2){
        c--;
        if (c<0||mn[r][c]==-1){
            c++;
            awa=1;
        }
    }
    if(jd==3){
        r--;
        if (r<0||mn[r][c]==-1){
            r++;
            awa=1;
        }
    }
    if(awa==1){
        jd = jdd(jd);
    }
}while(awa!=0);

▌作者的話

初幾次寫這種程式想法和程式介紹，寫得不好的地方請您見諒
這段程式有很多可以修改的更好的地方，只不過為了更好理解
因此整體寫成這樣，各位可以研究如何不用這麼多IF讓它行走
且符合題目需求，跟jd的0、1、2、3有關，提示:使用陣列做
希望這篇文章可以幫助到您，未來我會放更多更多的文章分享
我希望我的文章讓自己學習的同時也能幫助到別人，謝謝大家