資芽 北C 0409 作業講解

Ruby @Sprout2022


Outline


解題 SOP

NEOJ 987 - 大十字

NEOJ 938 - 3D迷宮


解題 SOP

NEOJ 987 - 大十字

NEOJ 938 - 3D迷宮


解題 SOP


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

理解題幹


閱讀題目時,留意:

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

算法設計


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

算法實作


  • 把邏輯上的算法數學化
  • 寫 code !

解題 SOP

NEOJ 987 - 大十字

NEOJ 938 - 3D迷宮


題幹理解


Neoj No. 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


解題 SOP

NEOJ 987 - 大十字

NEOJ 938 - 3D迷宮


題幹理解


Neoj No. 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


Thank you!

Ruby @Sprout 2022

Select a repo