西山居2024年秋招游戏开发A卷编程题

1.斐波那契

2.由0(海洋), 1(陆地), 2(有敌军的陆地)组成的二维网格, 计算没有敌军驻兵的岛屿数量。岛屿由水平或竖直方向相邻的陆地链接而成

#include <bits/stdc++.h>
using namespace std;
struct position
{
    int i;
    int j;
    position(int i, int j) {
        this->i = i;
        this->j = j;
    }
};

bool PositionInIslands(int i, int j, vector<vector<position>> islands) {
    if(islands.size() == 0) return false;
    for(auto island : islands) {
        for(auto pos : island) {
            if(pos.i == i && pos.j == j)
                return true;
        }
    }
    return false;
}

void Find(int i, int j, vector<vector<int>>& data, vector<position>& island) {
    data[i][j] = 0;

    island.emplace_back(position(i, j));
    int n = data.size();
    int m = data[0].size();

    if(i - 1 >= 0 && data[i - 1][j] != 0) Find(i-1, j, data, island);
    if(i + 1 < n && data[i + 1][j] != 0) Find(i+1, j, data, island);
    if(j - 1 >= 0 && data[i][j - 1] != 0) Find(i, j - 1, data, island);
    if(j + 1 < m && data[i][j + 1] != 0) Find(i, j + 1, data, island);
}


int CountEmptyIsland(vector<vector<int>>& data) {
    // 复制用于最后判定
    vector<vector<int>> copy_data(data);
    // 组成岛屿的位置
    vector<vector<position>> islands;
    for(int i = 0; i < data.size(); ++i) {
        for(int j = 0; j < data[0].size(); ++j) {
            // 是陆地
            if(data[i][j] == 1 || data[i][j] == 2) {
                // 陆地不包含在其他岛屿
                if(!PositionInIslands(i, j, islands)) {
                    vector<position> island;
                    // 找相邻陆地构成的岛屿
                    Find(i, j, data, island);
                    islands.emplace_back(island);
                }
            }
        }
    }

    int ans = islands.size();
    for(auto island : islands) {
        for(auto pos : island) {
            if(copy_data[pos.i][pos.j] == 2) {
                ans--;
                break;
            }
        }
    }

    return ans;
}

int main(void) {
    int n, m;
    cin >> n;
    cin >> m;
    vector<vector<int>> data(n, vector<int>(m));
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            cin >> data[i][j];
        }
    }

    cout << CountEmptyIsland(data) << endl;
    return 0;
}

3.实现简单的网络协议解码器, 从标准输入得到模拟的网络字节流, 对其解码并输出解析后的内容  

|检验码 2bytes|长度 2bytes|协议号 2bytes|消息体 n bytes|

字节流前两个字节为常量, 设置为"SS"

接下来两个字节为协议的长度 unsigned short

接着是两个字节的协议号 unsigned short

最后是消息  

每个字节流输入可能有多条协议, 并且最后一条协议不一定完整, 需要进行解码并输出.

如果有多条协议, 解析出字节流内完整的协议, 然后每条协议输出一行.  

#include <bits/stdc++.h>

using namespace std;

uint16_t CharToUint(char c) {
    uint16_t i = 0;
    if (isdigit(c)) {
        i += c - '0';
    } else {
        i += c - 'a' + 10;
    }
    return i;
}

uint16_t StrToUint(string str) {
    uint16_t i = 0;
    // index 1,0,3,2
    i += CharToUint(str[1]);
    i += CharToUint(str[0]) * 16;
    i += CharToUint(str[3]) * 16 * 16;
    i += CharToUint(str[2]) * 16 * 16 * 16;

    return i;
}

void Split(string message, vector<string>& messages) {
    uint16_t len;
    while (message.substr(0, 4) == "5353") {
        // 解码长度
        len = StrToUint(message.substr(4, 4));
        // 是否完整
        if (message.size() - 8 >= len) {
            messages.push_back(message.substr(8, len * 2));
            message = message.substr(8 + len * 2, message.size() - 8 - len * 2);
        } else {
            break;
        }
    }
}

void Decode(string m) {
    uint16_t num;
    string body = "";
    num = StrToUint(m.substr(0, 4));

    // 减去协议号
    m = m.substr(4, m.size() - 4);
    // 每两个字符进行解码
    for (int i = 0; i < m.size(); i += 2) {
        char c = 0;
        c += CharToUint(m[i + 1]);
        c += CharToUint(m[i]) * 16;
        body += c;
    }
    cout << num << " " << body << endl;
}


int main(void) {
    // 示例1
    // string message = "53530e00420048656c6c6f2053656153756e";
    // 示例2
    // string message =
    // "53530e00420048656c6c6f2053656153756e53531300580057656c636f6d6520746f205a6875486169";
    // 示例3
    string message =
        "53530e00420048656c6c6f2053656153756e53531300580057656c636f6d6520746f20"
        "5a687548616953530b007b00476f6f64206c75636b53530f00";
    vector<string> messages;

    Split(message, messages);

    for (string str : messages) {
        Decode(str);
    }

    return 0;
}