[已解决]求跑看看这段代码有什么问题

梦竹风

先扣掉上面的-1  发现图未分块  接下来扣掉右 发现分块了 判断第二块的权值嗯 我选择吃（本来我是打算先不管）  扣掉下 没分块  扣掉左 分块了 判断 blabla  
嗯我也是刚发现扣掉一个后可能并不只分成两块 也可能是三块 四块   

人造人

嗯，我研究研究

人造人

这题目有没有说输入数据的规模？
还有，多发几组样例输入和输出
这题目有点意思，我要研究研究
^_^

梦竹风

人造人 发表于 2021-12-5 20:32
这题目有没有说输入数据的规模？
还有，多发几组样例输入和输出
这题目有点意思，我要研究研究

Input

多组测试数据，空行隔开。
每组测试数据，第一行三个整数分别是方阵宽度N（1 <= N <= 8）,主角C起点坐标所在行号X，列号Y（1 <= X,Y <= N）；接下来是N行的方阵数据，对应方阵上每个豆豆的积分值，正数表示微笑豆豆增加的积分，负数表示忧郁豆豆扣除的积分。

Output

主角C能够获得的最大积分值。

Sample Input


2 1 1
10 -1
-2 10

3 2 3
1 1 1
-1000 -20 1
6 -5 1
Sample Output


19
6



很遗憾 只有这些

梦竹风

人造人 发表于 2021-12-5 20:32
这题目有没有说输入数据的规模？
还有，多发几组样例输入和输出
这题目有点意思，我要研究研究

Description

吃豆豆是80后童年经典小游戏之一，贪吃的主角C在方格子里头移动，吃掉无辜的豆豆获得相应积分。程序员v2决定给主角C增加点游戏难度：
1. 主角C被限制在一块NxN的方阵里头移动，每次只能往“上下左右”某个方向移动，且不能移出方阵边界，每个格子可以重复走动；
2. 方阵中每个格子都放着豆豆，每个豆豆带有相应的积分值；
3. 豆豆分两类，微笑豆豆和忧郁豆豆；
4. 吃掉微笑豆豆，主角C增加相应积分值；
5. 吃掉忧郁豆豆，主角C损失相应积分值；
6. 主角C可以随时结束游戏，只要它觉得这时候的积分值够大啦；
7. 主角C的起点坐标由程序随机指定，处于起点位置方格的豆豆必须吃掉。
根据以上规则，给定豆豆初始布局，请机智的你帮主角C写个程序吃掉合适位置的豆豆们得到最大的积分值吧。

人造人

明天有事，要先睡了
这个代码实现了搜索两点之间最优的那条路径
剩下的部分明天找时间写
这代码是一次写成的，没有调试
问题是居然没问题，不敢相信，^_^
我已经测试了几组数据，没有发现问题
如果有兴趣的话，帮忙多测试几组数据，看看是不是真的没问题

关于注释，一开始还在写，写着写着就不想写了，如果哪里看不懂就提出来
关于取名字，C++中基本上得给类型取名字，用 using 取名字，不然名字太长了
但是要想一个合适的名字太难了

1. #include <iostream>
   
2. #include <vector>
   
3. #include <algorithm>
   
4. 
   
5. // 矩阵，就一二维数组
   
6. using matrix_t = std::vector<std::vector<ssize_t>>;
   
7. // 一个标记，递归的时候需要知道哪些元素已经访问过了
   
8. using matrix_mark_t = std::vector<std::vector<bool>>;
   
9. // 矩阵中的点，这里只保存点的y值和x值
   
10. using point_t = std::pair<size_t, size_t>;
    
11. // 一个路径，就是一堆有顺序的点
    
12. using path_t = std::vector<point_t>;
    
13. 
    
14. bool operator==(const point_t &lhs, const point_t &rhs) {
    
15.     return lhs.first == rhs.first && lhs.second == rhs.second;
    
16. }
    
17. 
    
18. // 判断给定点是否有效，是否可以用给定点访问矩阵
    
19. bool point_valid(const matrix_t &data, const point_t &point) {
    
20.     if(data.size() <= point.first) return false;
    
21.     if(data[0].size() <= point.second) return false;
    
22.     return true;
    
23. }
    
24. 
    
25. // 获取指定路径上的值
    
26. ssize_t get_path_value(const matrix_t &data, const path_t *path) {
    
27.     ssize_t result = 0;
    
28.     for(const auto &i: *path) {
    
29.         result += data[i.first][i.second];
    
30.     }
    
31.     return result;
    
32. }
    
33. 
    
34. // 在4条路径上面选一个最大的
    
35. const path_t *select_path(const matrix_t &data, const path_t *top_path, const path_t *bottom_path, const path_t *left_path, const path_t *right_path) {
    
36.     ssize_t top_value = get_path_value(data, top_path);
    
37.     ssize_t bottom_value = get_path_value(data, bottom_path);
    
38.     ssize_t left_value = get_path_value(data, left_path);
    
39.     ssize_t right_value = get_path_value(data, right_path);
    
40.     std::vector<std::pair<const path_t *, ssize_t>> temp;
    
41.     if(top_path->size()) temp.push_back(std::pair<const path_t *, ssize_t>{top_path, top_value});
    
42.     if(bottom_path->size()) temp.push_back(std::pair<const path_t *, ssize_t>{bottom_path, bottom_value});
    
43.     if(left_path->size()) temp.push_back(std::pair<const path_t *, ssize_t>{left_path, left_value});
    
44.     if(right_path->size()) temp.push_back(std::pair<const path_t *, ssize_t>{right_path, right_value});
    
45.     if(!temp.size()) return NULL;
    
46.     std::sort(temp.begin(), temp.end(), [](const auto &a, const auto &b) -> bool {return a.second > b.second;});
    
47.     return temp[0].first;
    
48. }
    
49. 
    
50. // 返回从开始点到结束点之间的所有路径中值最大的那条路径
    
51. const path_t get_max_path(const matrix_t &data, matrix_mark_t &matrix_mark, const point_t &begin_point, const point_t &end_point) {
    
52.     path_t result; result.push_back(begin_point);
    
53.     if(begin_point == end_point) return result;
    
54.     matrix_mark[begin_point.first][begin_point.second] = true;
    
55.     path_t top_path;
    
56.     point_t top_point = point_t{begin_point.first - 1, begin_point.second};
    
57.     if(point_valid(data, top_point) && !matrix_mark[top_point.first][top_point.second]) {
    
58.         top_path = get_max_path(data, matrix_mark, top_point, end_point);
    
59.     }
    
60.     path_t bottom_path;
    
61.     point_t bottom_point = point_t{begin_point.first + 1, begin_point.second};
    
62.     if(point_valid(data, bottom_point) && !matrix_mark[bottom_point.first][bottom_point.second]) {
    
63.         bottom_path = get_max_path(data, matrix_mark, bottom_point, end_point);
    
64.     }
    
65.     path_t left_path;
    
66.     point_t left_point = point_t{begin_point.first, begin_point.second - 1};
    
67.     if(point_valid(data, left_point) && !matrix_mark[left_point.first][left_point.second]) {
    
68.         left_path = get_max_path(data, matrix_mark, left_point, end_point);
    
69.     }
    
70.     path_t right_path;
    
71.     point_t right_point = point_t{begin_point.first, begin_point.second + 1};
    
72.     if(point_valid(data, right_point) && !matrix_mark[right_point.first][right_point.second]) {
    
73.         right_path = get_max_path(data, matrix_mark, right_point, end_point);
    
74.     }
    
75.     matrix_mark[begin_point.first][begin_point.second] = false;
    
76.     const path_t *path = select_path(data, &top_path, &bottom_path, &left_path, &right_path);
    
77.     if(path) result.insert(result.end(), path->begin(), path->end());
    
78.     return result;
    
79. }
    
80. 
    
81. std::ostream &operator<<(std::ostream &os, const path_t &rhs) {
    
82.     bool flag = false;
    
83.     for(const auto &i: rhs) {
    
84.         if(flag) os << std::endl;
    
85.         os << "(" << i.second << "," << i.first << ")";
    
86.         flag = true;
    
87.     }
    
88.     return os;
    
89. }
    
90. 
    
91. int main() {
    
92.     matrix_t data;
    
93.     size_t n, x, y; std::cin >> n >> x >> y;
    
94.     --x; --y;
    
95.     for(size_t y = 0; y < n; ++y) {
    
96.         data.push_back(std::vector<ssize_t>());
    
97.         for(size_t x = 0; x < n; ++x) {
    
98.             ssize_t temp; std::cin >> temp;
    
99.             data[y].push_back(temp);
    
100.         }
     
101.     }
     
102.     matrix_mark_t matrix_mark(n, std::vector<bool>(n, false));
     
103.     path_t path = get_max_path(data, matrix_mark, point_t{y, x}, point_t{0, 0});
     
104.     std::cout << path << std::endl;
     
105.     return 0;
     
106. }
     

复制代码

梦竹风

早上起来想了以下 发现贪心算法确实不是最优解
有例子
4 1 1
1 -30 100 -9
-9 -9 -9 -9
-9 -9 -9 -9
-9 -9 -9 -9

梦竹风

emmmm 我裂开来了  我一开始的dfs算法也算一种贪心算法
遇到
3 2 2
1 -2 3
-4 5 -6
7 -8 9
就错了   正确答案应该是15 可是我的算法算不出15   呜呜呜

梦竹风

人造人 发表于 2021-12-5 23:59
明天有事，要先睡了
这个代码实现了搜索两点之间最优的那条路径
剩下的部分明天找时间写

hxd  c++写的少   复制过来提示 ssize_t 没定义呀

人造人

还需要点时间

梦竹风

emm最近做这道题花了不少时间咯  现在也要期末了 得预习一下准备期末考了 先不死磕这题了

人造人

梦竹风 发表于 2021-12-6 13:20
emmmm 我裂开来了  我一开始的dfs算法也算一种贪心算法
遇到
3 2 2

不行，我也写不出来
对于这个例子，我这边得到的是 13
对于这个题目，我没有思路了
我也放弃这个题目了