---
title: Sprout C-Taipei 0409 HW
tags: Sprout
type: slide
---

<style>
.dbg {
color: white;
background: rgba(255,255,255, 0.25);
border-radius: 1rem;
text-align: center;
}
.sdbg {
color: white;
background: rgba(255,255,255, 0.25);
border-radius: 1rem;
box-shadow: 0 0 20px #5680db;
text-shadow:
0 0 80px rgb(192 219 255 / 90%),
0 0 32px rgb(65 120 255 / 90%);
text-align: center;
}
.gt {
background:
linear-gradient(
to right, #30CFD0, #c43ad6
);
-webkit-background-clip: text;
-webkit-text-fill-color: transparent;
}

.warning {
color: red;
font-weight: bold;
}
body {
font-family: 'Courier New', monospace;
}
.rd {
border-radius: 2rem;
}
</style>

## 資芽 北C 0409 作業講解

<p class="gt">
Ruby @Sprout2022
</p>

----

## Outline

----

<p class="dbg">
解題 SOP
</p>
<p class="dbg">
NEOJ 987 - 大十字
</p>
<p class="dbg">
NEOJ 938 - 3D迷宮
</p>

---

<p class="sdbg">
解題 SOP
</p>
<p class="dbg">
NEOJ 987 - 大十字
</p>
<p class="dbg">
NEOJ 938 - 3D迷宮
</p>

----

### 解題 SOP

***

1. 題幹理解
2. 算法設計
3. 算法實作
4. 程式除錯

----

### 理解題幹

***

閱讀題目時，留意：

- 題幹情境
- 可利用資源
- 輸出要求
- 算法提示

----

### 算法設計

***

- 整理閱讀題目時的想法
- 歸納出邏輯緊密的解方
- 若算法過於複雜
- 拿紙筆視覺化想法
- 以人腦處理小規模測資

----

### 算法實作

***

- 把邏輯上的算法數學化
- 寫 code ！

---

<p class="dbg">
解題 SOP
</p>
<p class="sdbg">
NEOJ 987 - 大十字
</p>
<p class="dbg">
NEOJ 938 - 3D迷宮
</p>

----

### 題幹理解

***


[Neoj No. 987](https://neoj.sprout.tw/problem/987/)

----

### 算法設計

***

1. 接收所有位置相對應的座號
2. 接收被叫到的座號
3. 找到被叫到座號的人相對應之位置
4. 找到所有在此位置之大字上的位置
5. 找到這些位置相對應座號中的最大值

----

### 算法實作

***

1. 接收二整數 $m, n$
2. 接收一整數矩陣 $M_{m\times n}$
3. 接收一整數 $k$
4. 找到 $k$ 在 $M_{m\times n}$ 中的位置 $(r, c)$
5. 找出 $(r, c)$ **大十字**中之最大值

----


----

$\text{Let }S\text{ the set of numbers that}$
$\text{sit on the cross of }(r, c)\text{ in }M_{m\times n}$

$S=\{M_{ij}\}\text{, where}i, j\in N\text{ must satisfy}$

- $(i, j)\ne(r, c)$
- $(i=r, 0\le j<n)\lor(j=c, 0\le i<m)$

----

Write Code!

***

#include <iostream>

using namespace std;

int main() {
    /* Reading input */
    int m, n, target, nums[100][100];
    cin >> m >> n;
    for (int i = 0; i < m; ++i)
        for (int j = 0; j < n; ++j)
            cin >> nums[i][j];
    cin >> target;

    /* Finding (r, c) of the target */
    int r, c;
    for (int i = 0; i < m; ++i) {
        bool found = false;
        for (int j = 0; j < n; ++j)
            if (nums[i][j] == target) {
                r = i, c = j, found = true;
                break;
            }
        if (found) break;
    }

    /* Finding the max. among the numbers of those who have to stand up */
    int maxNum = 0;
    for (int i = 0; i < m; ++i) // column
        if (i != r) maxNum = max(maxNum, nums[i][c]);   
    for (int j = 0; j < m; ++j) // row
        if (j != c) maxNum = max(maxNum, nums[r][j]); 
    
    cout << maxNum << '\n';
    return 0;
}

[Source Code](https://gist.github.com/ruby0322/9dd4ed2c65935eede474b5afe2852cd3)

---

<p class="dbg">
解題 SOP
</p>
<p class="dbg">
NEOJ 987 - 大十字
</p>
<p class="sdbg">
NEOJ 938 - 3D迷宮
</p>

----

### 題幹理解

***


[Neoj No. 938](https://neoj.sprout.tw/problem/938/)

----


----

### 算法設計

***

1. 接收迷宮資訊
2. 接收起始座標
3. 接收心中指示
4. 驗證心中指示
- 若合法則執行
- 不合法則撤銷，並輸出 `Ooops!!!`
5. 輸出最終座標

----

### 算法實作

***

- 接收三整數 $x, y, z$
- 接收 $xyz$ 個整數 $a_i$
- $0\le i<xyz\land i\in \mathbb Z$
- $a_i\in\{0, 1\}$
- $a_i$ 對應 ($i\mod x, \lfloor{i\over x}\rfloor \mod y, \lfloor {i\over xy}\rfloor$)
- 接收三整數 $q,w,e$
- $0\le q<x, 0\le w<y, 0\le e<z$
- 接收一整數 $m$
- $1\le m\le 100$
- 接收 $m$ 個整數 $k_i$
- $0\le i<m\land i\in\mathbb Z$
- $k_i\in\{1,2,3,4,5,6\}$

----

(續上頁)

- 每接收一個 $k_i$ ，驗證相對應指令的可行性
- 可行：照做
- 不可行：撤銷並印出 "Ooops!!!"
- 輸出最終位置

----

Write Code!

***

#include <iostream>

using namespace std;

bool isWall[100][100][100];
char input[1000001];

int main() {
    
    int x, y, z, q, w, e, m;
    cin >> x >> y >> z;

    cin >> input;

    int n = x*y*z;
    for (int i = 0; i < n; ++i)
        isWall[i % x][(i/x) % y][i / (x*y)] = static_cast<bool>(input[i] - '0');
    
    cin >> q >> w >> e >> m;

    for (int i = 0; i < m; ++i) {
        int k, newX = q, newY = w, newZ = e;
        cin >> k;

        if      (k == 1) ++newX;
        else if (k == 2) --newX;
        else if (k == 3) --newY;
        else if (k == 4) ++newY;
        else if (k == 5) ++newZ;
        else if (k == 6) --newZ;    

        // cout << "(" << newX << "," << newY << "," << newZ << ")" << endl;

        if (newX < 0 || newX >= x || newY < 0 || newY >= y || newZ < 0 || newZ >= z || isWall[newX][newY][newZ]) {
            cout << "Ooops!!!" << endl;
            continue;
        }

        q = newX, w = newY, e = newZ;
    }

    cout << q << " " << w << " " << e << endl;
}

[Source Code](https://gist.github.com/ruby0322/bfca1f703a41bc1257e5e151ddbe9bdb)

---

<!-- .slide: data-background="#FFFFFF" -->

Thank you!

##### <p class="gt">Ruby @Sprout 2022</p>