ZeroJudge M932: 蜜蜂觀察

蜜蜂 Bob 在一個大小是 M＊N 的蜂巢 (見下圖），並且每個蜂巢格上會有一個代表字母 (大或小寫英文字母)。

Bob 一開始在蜂巢左下角，行走方向定義如圖：

  • 0 是往右上
  • 1 是往右邊
  • 2 是往右下
  • 3 是往左下
  • 4 是往左邊
  • 5 是往左上
ZeroJudge M932: 蜜蜂觀察 蜂巢方向定義圖

輸入每步移動的方向，請輸出經過的路徑每格的代表字母，以及經過字元的種類數（大小寫相異），若經過時碰到牆壁該行動會停在原地。

範例測資

範例輸入範例輸出
第一行包含三個整數 M、N、K (1 <= M, N <= 20、1 <= K <= 100)，表示蜂巢的大小是 M＊N，Bob 的行走路徑有 K 步。
接下來的 M 行，每行包含 N 個字母 (大小寫英文字母)，代表蜂巢的狀態。
最後一行包含 K 個整數，表示 Bob 的移動路徑方向。		輸出包含兩個部分 (各一行)：
1. 由 Bob 每步經過的每格代表字母所組成的字串。
2. 經過字元的種類數（大小寫視為相異），用一個整數表示。
2 4 5
TyuI
ABaB
0 1 2 3 0		Tyaau
4
4 6 11
rMmnis
LRveEX
ZexDoc
HAdbHA
0 1 5 1 1 0 3 0 0 1 0		ZeLRvmvmmnn
7

解題思路

本題比較複雜的地方是因為題目的結構是蜂巢狀，但是收資料的時候是採正方形的方式。

但是可以理解為：

  • 右上的時候 x 和 y 值的變化為 (0, -1)
  • 右邊的時候為 (1, 0)
  • 右下的時候為 (1, 1)
  • 左下的時候為 (0, 1)
  • 左邊的時候為 (-1, 0)
  • 左上的時候為 (-1, -1)

如果不理解的話可以拿範例一的資料用畫的方式畫畫看 (如下圖) 就會大概知道這個概念。需要注意的是每次行走時都需要判斷這樣子走會不會超出陣列的邊界。輸出次數的部分可以使用 Map 來存已經出現過的字元。

ZeroJudge M932: 蜜蜂觀察 範例一解釋－解題思路

範例程式碼－ZeroJudge M932: 蜜蜂觀察

#include <iostream>
#include <map>
#include <vector>
using namespace std;

pair<int, int>rtn (int a, int b)
{
    pair<int, int>tmp;
    tmp.first = a;
    tmp.second = b;
    return tmp;
}

int main() {
    int M, N, K;
    cin >> M >> N >> K;
    cin.ignore();
    vector<string>v;
    for (int i = 0; i<M; i++)
    {
        string tmp;
        getline(cin, tmp);
        v.push_back(tmp);
    }
    int x = 0, y = M-1;
    map<int, pair<int, int>>MAP;
    MAP[0] = rtn(0, -1);
    MAP[1] = rtn(1, 0);
    MAP[2] = rtn(1, 1);
    MAP[3] = rtn(0, 1);
    MAP[4] = rtn(-1, 0);
    MAP[5] = rtn(-1, -1);
    map<char, int>appear;
    int ans = 0;
    for (int i = 0; i<K; i++)
    {
        int tmp;
        cin >> tmp;
        int xx = x + MAP[tmp].first, yy = y + MAP[tmp].second;
        //cout << xx << " " << yy;
        if (xx >= 0 && xx < N && yy >= 0 && yy < M)
        {
            x = xx;
            y = yy;
            char ch = v[y][x];
            if (isalpha(ch))
            {
                cout << ch;
                if (appear[ch] == 0) ans++;
                appear[ch]++;
            }
        }
        else
        {
            char ch = v[y][x];
            if (isalpha(ch))
            {
                cout << ch;
                if (appear[ch] == 0) ans++;
                appear[ch]++;
            }
        }
    }
    cout << "\n" << ans << "\n";
}

//ZeroJudge M932
//Dr. SeanXD
標籤

相關文章

發佈留言