<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!
***
```cpp
#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!
***
```cpp
#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>
{"metaMigratedAt":"2023-06-16T22:30:49.382Z","metaMigratedFrom":"YAML","title":"Sprout C-Taipei 0409 HW","breaks":true,"contributors":"[{\"id\":\"7f2869ec-74af-417d-af08-3133a06727e3\",\"add\":5751,\"del\":153}]"}