# APCS實作題2022年10月第2題：運貨站

> 日期：2023年10月2日
> 作者：王一哲
> 題目來源：111年10月實作題第2題
> [ZeroJudge 題目連結](https://zerojudge.tw/ShowProblem?problemid=j123)

<br />

## 題目

### 問題描述

運貨站要管理 $n$ 個五種不同形狀的貨物，下圖標示出貨物的形狀以及對應的英文代碼。

<img height="60%" width="60%" src="https://imgur.com/oHjTX9f.png" style="display: block; margin-left: auto; margin-right: auto;"/>
<br />

現在這 $n$ 個貨物要按照順序堆放在一個容量大小為 $R \times C$ 的倉庫內，第 $i$ 個貨物的形狀為 $t_i$，並且和倉庫的頂部距離為 $y_i$ (見圖ㄧ)。貨物堆放置倉庫內時必須維持和倉庫頂端的高度由右向左推到不能前進為止，並且過程中不行將貨物的方向做旋轉。若有一個貨物不能完整放入倉庫內，則該貨物會被貨運站丟棄。

請輸出依序放完這 $n$ 個貨物後，倉庫內有多少剩餘空格，以及被丟棄的貨物有幾個。

<img height="50%" width="50%" src="https://imgur.com/P93advE.png" style="display: block; margin-left: auto; margin-right: auto;"/>
<div style="text-align:center">圖一：該貨物類別為B，並且離倉庫頂端距離為2。保證輸入內貨物距離倉庫頂部的高度不會讓貨物底部低於地面，並且不會有任何貨物卡在倉庫門口的情形。</div>
<br />

### 輸入說明

第一行輸入三個數字 $R (1 \leq R \leq 30)$, $C (1 \leq C \leq 50)$, $n (1 \leq n \leq 200)$，代表倉庫大小為 $R \times C$ 以及有 $n$ 個貨物。接下來有 $n$ 行，第 $i$ 行有一個大寫英文字母 $t_i$ 和一個數字 $y_i$ 代表貨物的種類以及和倉庫頂部的距離，貨物種類只會是A到E的大寫字母。

子題配分
- 20%：只會出現B類型
- 40%：只會出現A、B、C類型
- 40%：5種類型都會出現

<br />

### 輸出說明

輸出倉庫剩餘的空格數量，以及被丟棄的貨物數量。
<br />

### 範例一：輸入

5 4 6
B 0
B 3
B 1
B 3
B 1
B 2

### 範例一：正確輸出

8 2

<br />

### 範例二：輸入

5 6 6
C 1
A 1
E 0
E 0
B 0
A 0

### 範例二：正確輸出

13 2

<br />

## Python 程式碼

以下的程式碼是參考[這個網頁](https://coding-prep.com/2023/02/02/2022-%e5%b9%b4-10-%e6%9c%88-apcs-%e9%a1%8c%e8%a7%a3/)，再改寫成 Python 版本。於 ZeroJudge 測試結果，最長運算時間約為 39 ms，使用記憶體最多約為 3.6 MB，通過測試。

# 方塊的基準點為右上角的點
R, C, n = map(int, input().split())  # 讀取地圖列數R、行數C、貨物數量n
maps = [[0]*C for _ in range(R)]  # 儲存地圖用的二維陣列，如果格子上沒有東西為0，有東西為1
discard, space = 0, R*C  # 分別為捨棄貨物數量、剩下的空格數量

def boxA(row):  # A 類貨物
    global maps, discard, space
    flag = False  # 是否被捨棄，預設為 False
    c = C-1  # 記錄貨物放入的行號
    # 由地圖最右側的行開始測試，如果這幾格已經有貨物則中斷迴圈；flag 設定為 True，變數 c 設定為 i
    for i in range(C-1, -1, -1):
        if maps[row][i] or maps[row+1][i] or maps[row+2][i] or maps[row+3][i]: break
        else: flag = True; c = i
    # 如果可以放入貨物，將格子設定為1，空格數減4；如果不能放入，discard 加1
    if flag:
        maps[row][c] = 1; maps[row+1][c] = 1; maps[row+2][c] = 1; maps[row+3][c] = 1
        space -= 4
    else: discard += 1
        
def boxB(row):  # B 類貨物
    global maps, discard, space
    flag = False  # 是否被捨棄，預設為 False
    c = C-1  # 記錄貨物放入的行號
    # 由地圖最右側的行開始測試，如果這幾格已經有貨物則中斷迴圈；flag 設定為 True，變數 c 設定為 i
    for i in range(C-1, 1, -1):
        if maps[row][i] or maps[row][i-1] or maps[row][i-2]: break
        else: flag = True; c = i
    # 如果可以放入貨物，將格子設定為1，空格數減3；如果不能放入，discard 加1
    if flag:
        maps[row][c] = 1; maps[row][c-1] = 1; maps[row][c-2] = 1
        space -= 3
    else: discard += 1
        
def boxC(row):  # C 類貨物
    global maps, discard, space
    flag = False  # 是否被捨棄，預設為 False
    c = C-1  # 記錄貨物放入的行號
    # 由地圖最右側的行開始測試，如果這幾格已經有貨物則中斷迴圈；flag 設定為 True，變數 c 設定為 i
    for i in range(C-1, 0, -1):
        if maps[row][i] or maps[row][i-1] or maps[row+1][i] or maps[row+1][i-1]: break
        else: flag = True; c = i
    # 如果可以放入貨物，將格子設定為1，空格數減4；如果不能放入，discard 加1
    if flag:
        maps[row][c] = 1; maps[row][c-1] = 1; maps[row+1][c] = 1; maps[row+1][c-1] = 1
        space -= 4
    else: discard += 1

def boxD(row):  # D 類貨物
    global maps, discard, space
    flag = False  # 是否被捨棄，預設為 False
    c = C-1  # 記錄貨物放入的行號
    # 由地圖最右側的行開始測試，如果這幾格已經有貨物則中斷迴圈；flag 設定為 True，變數 c 設定為 i
    for i in range(C-1, 1, -1):
        if maps[row][i] or maps[row+1][i-2] or maps[row+1][i-1] or maps[row+1][i]: break
        else: flag = True; c = i
    # 如果可以放入貨物，將格子設定為1，空格數減4；如果不能放入，discard 加1
    if flag:
        maps[row][c] = 1; maps[row+1][c-2] = 1; maps[row+1][c-1] = 1; maps[row+1][c] = 1
        space -= 4
    else: discard += 1

def boxE(row):  # E 類貨物
    global maps, discard, space
    flag = False  # 是否被捨棄，預設為 False
    c = C-1  # 記錄貨物放入的行號
    # 由地圖最右側的行開始測試，如果這幾格已經有貨物則中斷迴圈；flag 設定為 True，變數 c 設定為 i
    for i in range(C-1, 0, -1):
        if maps[row][i] or maps[row+1][i-1] or maps[row+1][i] or maps[row+2][i-1] or maps[row+2][i]: break
        else: flag = True; c = i
    # 如果可以放入貨物，將格子設定為1，空格數減5；如果不能放入，discard 加1
    if flag:
        maps[row][c] = 1; maps[row+1][c-1] = 1; maps[row+1][c] = 1; maps[row+2][c-1] = 1; maps[row+2][c] = 1
        space -= 5
    else: discard += 1

# 主要解題過程
for _ in range(n):  # 讀取n行貨物資料
    tmp = input().split()  # 讀取資料
    t = tmp[0]  # 貨物種類
    r = int(tmp[1])  # 貨物頂與倉庫頂的距離
    if t == 'A': boxA(r)   # 依照貨物種類呼叫對應的自訂函式
    elif t == 'B': boxB(r)
    elif t == 'C': boxC(r)
    elif t == 'D': boxD(r)
    elif t == 'E': boxE(r)
    #print(space, discard)  # 除錯用，空格及捨棄的貨物數量
    # 除錯用，印出地圖
    #for i in range(R):
    #    for j in range(C):
    #        print(maps[i][j], end=" " if j < C-1 else "\n")

# 印出答案
print(space, discard)

<br /><br />

## C++ 程式碼

於 ZeroJudge 測試結果，最長運算時間約為 9 ms，使用記憶體最多約為 340 kB，通過測試。

#include <iostream>
using namespace std;

// 方塊的基準點為右上角的點
int R, C, n, discard = 0, space;  // 地圖列數R、行數C、貨物數量n、捨棄貨物數量、剩下的空格數量
void boxA(int, int**);
void boxB(int, int**);
void boxC(int, int**);
void boxD(int, int**);
void boxE(int, int**);

int main() {
    cin >> R >> C >> n;
    space = R*C;
    int **maps;  // 儲存地圖用的二維陣列，如果格子上沒有東西為0，有東西為1
    maps = new int *[R];
    for(int i=0; i<R; i++) maps[i] = new int[C];
    for(int i=0; i<R; i++){
        for(int j=0; j<C; j++) {
            maps[i][j] = 0;
        }
    }
    
    for(int i=0; i<n; i++) {  // 讀取n行貨物資料
        char t; cin >> t;     // 貨物種類
        int r; cin >> r;      // 貨物頂與倉庫頂的距離
        switch(t) {
            case 'A':
                boxA(r, maps); break;
            case 'B':
                boxB(r, maps); break;
            case 'C':
                boxC(r, maps); break;
            case 'D':
                boxD(r, maps); break;
            case 'E':
                boxE(r, maps); break;
        }
    }
    cout << space << " " << discard << endl;  // 印出答案
    return 0;
}

void boxA(int row, int **maps) {  // A 類貨物
    bool flag = false;  // 是否被捨棄，預設為 False
    int c = C-1;  // 記錄貨物放入的行號
    // 由地圖最右側的行開始測試，如果這幾格已經有貨物則中斷迴圈；flag 設定為 true，變數 c 設定為 i
    for(int i = C-1; i > -1; i--) {
        if (maps[row][i] || maps[row+1][i] || maps[row+2][i] || maps[row+3][i]) {
            break;
        } else {
            flag = true; c = i;
        }
    }
    // 如果可以放入貨物，將格子設定為1，空格數減4；如果不能放入，discard 加1
    if (flag) {
        maps[row][c] = 1; maps[row+1][c] = 1; maps[row+2][c] = 1; maps[row+3][c] = 1; space -= 4;
     } else { discard++; }
}

void boxB(int row, int **maps) {  // B 類貨物
    bool flag = false;  // 是否被捨棄，預設為 False
    int c = C-1;  // 記錄貨物放入的行號
    // 由地圖最右側的行開始測試，如果這幾格已經有貨物則中斷迴圈；flag 設定為 true，變數 c 設定為 i
    for(int i = C-1; i > 1; i--) {
        if (maps[row][i] || maps[row][i-1] || maps[row][i-2]) {
            break;
        } else {
            flag = true; c = i;
        }
    }
    // 如果可以放入貨物，將格子設定為1，空格數減3；如果不能放入，discard 加1
    if (flag) {
        maps[row][c] = 1; maps[row][c-1] = 1; maps[row][c-2] = 1; space -= 3;
    } else { discard++; }
}

void boxC(int row, int **maps) {  // C 類貨物
    bool flag = false;  // 是否被捨棄，預設為 False
    int c = C-1;  // 記錄貨物放入的行號
    // 由地圖最右側的行開始測試，如果這幾格已經有貨物則中斷迴圈；flag 設定為 true，變數 c 設定為 i
    for(int i = C-1; i > 0; i--) {
        if (maps[row][i] || maps[row][i-1] || maps[row+1][i] || maps[row+1][i-1]) {
            break;
        } else {
            flag = true; c = i;
        }
    }
    // 如果可以放入貨物，將格子設定為1，空格數減4；如果不能放入，discard 加1
    if (flag) {
        maps[row][c] = 1; maps[row][c-1] = 1; maps[row+1][c] = 1; maps[row+1][c-1] = 1; space -= 4;
    } else { discard++; }
}

void boxD(int row, int **maps) {  // D 類貨物
    bool flag = false;  // 是否被捨棄，預設為 False
    int c = C-1;  // 記錄貨物放入的行號
    // 由地圖最右側的行開始測試，如果這幾格已經有貨物則中斷迴圈；flag 設定為 true，變數 c 設定為 i
    for(int i = C-1; i > 1; i--) {
        if (maps[row][i] || maps[row+1][i-2] || maps[row+1][i-1] || maps[row+1][i]) {
            break;
        } else {
            flag = true; c = i;
        }
    }
    // 如果可以放入貨物，將格子設定為1，空格數減4；如果不能放入，discard 加1
    if (flag) {
        maps[row][c] = 1; maps[row+1][c-2] = 1; maps[row+1][c-1] = 1; maps[row+1][c] = 1; space -= 4;
    } else { discard++; }
}

void boxE(int row, int **maps) {  // E 類貨物
    bool flag = false;  // 是否被捨棄，預設為 False
    int c = C-1;  // 記錄貨物放入的行號
    // 由地圖最右側的行開始測試，如果這幾格已經有貨物則中斷迴圈；flag 設定為 true，變數 c 設定為 i
    for(int i = C-1; i > 0; i--) {
        if (maps[row][i] || maps[row+1][i-1] || maps[row+1][i] || maps[row+2][i-1] || maps[row+2][i]) {
            break;
        } else {
            flag = true; c = i;
        }
    }
    // 如果可以放入貨物，將格子設定為1，空格數減5；如果不能放入，discard 加1
    if (flag) {
        maps[row][c] = 1; maps[row+1][c-1] = 1; maps[row+1][c] = 1; maps[row+2][c-1] = 1; maps[row+2][c] = 1; space -= 5;
    } else { discard++; }
}

<br /><br />

---

###### tags:`APCS`、`Python`、`C++`