分享一个我突发奇想的抽象但实用的算法

蒟蒻

需求：

在教室中，有8列6行共48个座位，你们班有48人，学号为1~48，他们每个人都随机坐在一个座位上（有这样一个二位数组classRoom[8][6]，共有48个元素，每个元素为1~48中任意一个整数，且每个数只能出现一次），你是一名课代表，手上有每一名同学的共48本作业，你从教室门口开始发作业，但是你每次只能看到最顶上三本（有这样一个homeworks[48]数组，共有48个元素，每个元素为1~48中任意一个整数，且每个数只能出现一次，你每次只能读取homeworks[0],homeworks[1],homeworks[2]三个元素），如果同学在你左右两侧或前后两侧，你可以把作业发给他（假设下标位于classRoom[x][y]，如果classRoom[x][y],classRoom[x+1][y],classRoom[x-1][y],classRoom[x][y+1],classRoom[x][y-1]中任意一个数据与homeworks[0],homeworks[1],homeworks[2]中任意一个数据相等，那么就可以弹出homeworks[0],homeworks[1],homeworks[2]中与classRoom中相等的数据）。你的移动方法：每次只能移动一步（假设下标位于classRoom[x][y]，那么每次移动只能出现classRoom[x+1][y],classRoom[x-1][y],classRoom[x][y+1],classRoom[x][y-1]四种情况）。课代表最少需要移动多少步才能发完作业（下标需要移动多少次才能使homeworks数组中的所有元素都被弹出）

我感觉还是挺有用的，我一个课代表天天发作业发得头晕
文心一言结果：

[C++] 纯文本查看 复制代码

#include <iostream>
#include <vector>
#include <queue>
#include <unordered_set>
#include <tuple>

using namespace std;

struct State {
    int x, y, steps;
    vector<int> hw; // Remaining homeworks
};

int minStepsToDistributeHomework(vector<vector<int>>& classRoom, vector<int>& homeworks) {
    int directions[4][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}}; // right, left, down, up
    int rows = classRoom.size();
    int cols = classRoom[0].size();
    
    unordered_set<int> hwSet(homeworks.begin(), homeworks.end());
    queue<State> q;
    unordered_set<tuple<int, int, string>> visited; // (x, y, hw state hash)
    
    // Start from the door (0, 0) with all homeworks
    q.push({0, 0, 0, homeworks});
    visited.insert({0, 0, to_string(hwSet)});
    
    while (!q.empty()) {
        State curr = q.front();
        q.pop();
        
        int x = curr.x;
        int y = curr.y;
        int steps = curr.steps;
        vector<int> hw = curr.hw;
        
        // If all homeworks are distributed, return the steps taken
        if (hw.empty()) {
            return steps;
        }
        
        // Try to match and distribute homework in the current position
        for (int i = 0; i < hw.size(); ++i) {
            if (hw[i] == classRoom[x][y]) {
                hw.erase(hw.begin() + i);
                break;
            }
        }
        
        // If homework is distributed, update the set and continue
        hwSet.clear();
        for (int hwId : hw) {
            hwSet.insert(hwId);
        }
        
        // Try moving in all four directions
        for (auto& dir : directions) {
            int nx = x + dir[0];
            int ny = y + dir[1];
            
            if (nx >= 0 && nx < rows && ny >= 0 && ny < cols) {
                // Try to match and distribute homework in the new position
                vector<int> newHw = hw;
                for (int i = 0; i < newHw.size(); ++i) {
                    if (newHw[i] == classRoom[nx][ny]) {
                        newHw.erase(newHw.begin() + i);
                        break;
                    }
                }
                
                // If new state is not visited, add to queue
                string newHwStr = to_string(unordered_set<int>(newHw.begin(), newHw.end()));
                if (visited.find({nx, ny, newHwStr}) == visited.end()) {
                    q.push({nx, ny, steps + 1, newHw});
                    visited.insert({nx, ny, newHwStr});
                }
            }
        }
    }
    
    // If we exit the loop, it means we couldn't distribute all homeworks (should never happen with valid input)
    return -1;
}

int main() {
    vector<vector<int>> classRoom = {
        // Example initialization, you should replace it with random seating arrangement
        {1, 2, 3, 4, 5, 6},
        {7, 8, 9, 10, 11, 12},
        {13, 14, 15, 16, 17, 18},
        {19, 20, 21, 22, 23, 24},
        {25, 26, 27, 28, 29, 30},
        {31, 32, 33, 34, 35, 36},
        {37, 38, 39, 40, 41, 42},
        {43, 44, 45, 46, 47, 48}
    };
    
    vector<int> homeworks = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48};
    // Shuffle homeworks array if needed to simulate randomness
    random_shuffle(homeworks.begin(), homeworks.end());
    
    int steps = minStepsToDistributeHomework(classRoom, homeworks);
    cout << "Minimum steps to distribute all homework: " << steps << endl;
    
    return 0;
}

deepseek结果：

[C++] 纯文本查看 复制代码

服务器繁忙，请稍后再试

蒟蒻

补deepseek结果：

[C++] 纯文本查看 复制代码

#include <iostream>
#include <queue>
#include <vector>
#include <unordered_set>
#include <tuple>

using namespace std;

// 教室的行数和列数
const int ROWS = 6;
const int COLS = 8;

// 定义状态结构体
struct State {
    int x, y; // 课代表的当前位置
    vector<int> homeworkStack; // 当前的作业堆
    int steps; // 已经移动的步数
    unordered_set<int> distributed; // 已经发完的作业
};

// 计算状态的哈希值
struct StateHash {
    size_t operator()(const State& state) const {
        size_t hash = 0;
        hash ^= hash<int>()(state.x) + 0x9e3779b9 + (hash << 6) + (hash >> 2);
        hash ^= hash<int>()(state.y) + 0x9e3779b9 + (hash << 6) + (hash >> 2);
        for (int hw : state.homeworkStack) {
            hash ^= hash<int>()(hw) + 0x9e3779b9 + (hash << 6) + (hash >> 2);
        }
        return hash;
    }
};

// 判断两个状态是否相等
struct StateEqual {
    bool operator()(const State& lhs, const State& rhs) const {
        return lhs.x == rhs.x && lhs.y == rhs.y && lhs.homeworkStack == rhs.homeworkStack;
    }
};

// BFS搜索函数
int bfs(const vector<vector<int>>& classRoom, const vector<int>& homeworks) {
    // 初始状态
    State initialState;
    initialState.x = 0; // 假设课代表从教室门口开始，位置为(0, 0)
    initialState.y = 0;
    initialState.homeworkStack = vector<int>(homeworks.begin(), homeworks.begin() + 3);
    initialState.steps = 0;
    initialState.distributed = unordered_set<int>();

    // BFS队列
    queue<State> q;
    q.push(initialState);

    // 记录已经访问过的状态
    unordered_set<State, StateHash, StateEqual> visited;
    visited.insert(initialState);

    // 定义四个移动方向
    int dx[] = {-1, 1, 0, 0};
    int dy[] = {0, 0, -1, 1};

    while (!q.empty()) {
        State current = q.front();
        q.pop();

        // 如果所有作业都已经发完，返回步数
        if (current.distributed.size() == 48) {
            return current.steps;
        }

        // 尝试向四个方向移动
        for (int i = 0; i < 4; ++i) {
            int nx = current.x + dx[i];
            int ny = current.y + dy[i];

            // 检查新位置是否在教室范围内
            if (nx >= 0 && nx < COLS && ny >= 0 && ny < ROWS) {
                // 检查是否可以发作业
                for (int j = 0; j < 3; ++j) {
                    if (current.homeworkStack[j] == classRoom[nx][ny]) {
                        // 发作业
                        State newState = current;
                        newState.x = nx;
                        newState.y = ny;
                        newState.distributed.insert(current.homeworkStack[j]);
                        newState.homeworkStack.erase(newState.homeworkStack.begin() + j);
                        if (newState.homeworkStack.size() < 3 && newState.steps + 1 < 48) {
                            newState.homeworkStack.push_back(homeworks[newState.steps + 1 + newState.distributed.size()]);
                        }
                        newState.steps++;

                        // 如果新状态没有被访问过，加入队列
                        if (visited.find(newState) == visited.end()) {
                            visited.insert(newState);
                            q.push(newState);
                        }
                    }
                }

                // 如果不能发作业，只是移动
                State newState = current;
                newState.x = nx;
                newState.y = ny;
                newState.steps++;

                // 如果新状态没有被访问过，加入队列
                if (visited.find(newState) == visited.end()) {
                    visited.insert(newState);
                    q.push(newState);
                }
            }
        }
    }

    return -1; // 如果没有找到解，返回-1
}

int main() {
    // 假设教室的座位分布
    vector<vector<int>> classRoom(COLS, vector<int>(ROWS));
    // 假设作业堆
    vector<int> homeworks(48);

    // 初始化教室座位和作业堆
    // 这里需要根据实际情况初始化classRoom和homeworks

    // 调用BFS函数计算最少步数
    int result = bfs(classRoom, homeworks);

    if (result != -1) {
        cout << "最少需要移动 " << result << " 步才能发完所有作业。" << endl;
    } else {
        cout << "无法发完所有作业。" << endl;
    }

    return 0;
}

Jbyccc

确实抽象

keykylewu

“无法发完所有作业”是什么情况？？

蒟蒻

keykylewu 发表于 2025-2-15 23:25
“无法发完所有作业”是什么情况？？

可能是课代表累了 罢工了

xiaomeng

有写代码那会功夫作业早发完了

蒟蒻

xiaomeng 发表于 2025-2-26 09:57
有写代码那会功夫作业早发完了

DeepSeek写代码可比我发作业快多了

xiaomeng

蒟蒻 发表于 2025-2-28 21:22
DeepSeek写代码可比我发作业快多了

deepseek写code一般般吧

System

这不是挺简单的搜索么dfs也行，要不你试试（突然的回归）