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

梦竹风

输入
3 2 3
1 1 1
-1000 -20 1
6 -5 1

输入解释  第一行分别为 n  x  y  接下来n行为一个方阵
x y 表示 起点从第x行第y列开始  需要注意的是 这里没有第零行  但是为了方便操作我在输入后自行对x 和 y进行自减

该程序大致步骤

输入方阵并初步初始化方阵的点

设置方阵内每个点的 v容器
该容器将存储该点周围的点的坐标        (在这一步就出错了)

从方阵的起点开始 合并以该起点为中心的周围的正权值点


若对程序哪部分语句不太理解可以提出


#include"iostream"
#include"vector"
#include"algorithm"

using namespace std;


typedef struct Point
{
        int x;
        int y;
        int p;        //该点的积分
        int isto;        //单次寻路该节点是否已达
        int mp;        //在单次寻路中,能够到达该点的最大积分
        int temp;        //暂存积分值
        Point* h;        //最佳前驱节点
        Point* nh;        //当前路的前驱节点
        int id;        //标明该点位于第几个积分区域
        vector<Point*> v;        //该容器存储周围的点
}Point;

typedef struct
{
        int id;
        int p;        //该区域的积分
        int isto;        //似乎无用
        int mp;        //似乎无用
        int temp;        //似乎无用
        vector<Point*> v;        //该区域内的边缘点
}Block;

Point* mallocPoint(int x, int y, int p)
{
        Point* g;
        g = (Point*)malloc(sizeof(Point));
        g->x = x;
        g->y = y;
        g->p = p;
        g->isto = 0;
        g->mp = 0;
        g->temp = 0;
        g->h = nullptr;
        g->nh = nullptr;
        g->id = -1;
        return g;
}

Block* mallocBlock(int id)
{
        Block* b;
        b = (Block*)malloc(sizeof(Block));
        b->id = id;
        b->p = 0;
        b->isto = 0;
        b->mp = 0;
        b->temp = 0;
       
        return b;

}


void function1(int n, int x, int y);
Block* merge(Point* p, int id);
void setv(Point*** p, Point* g, int n);



int main()
{
        int n, x, y;
        while (cin >> n >> x >> y)
        {
                function1(n, x, y);
        }

}


void function1(int n, int x, int y)
{
        Point*** p;
        vector<Block*>b;

        int temp;
        int i, j;
        Point* maxP;

        x--;
        y--;

        p = (Point***)malloc(sizeof(Point**) * n);
        p[0] = (Point**)malloc(sizeof(Point*) * n * n);
        for (i = 0; i < n; i++)
        {
                p[i] = p[0] + n * i;
        }



        //设置地图积分值
        //设置点未达
        for (i = 0; i < n; i++)
        {
                for (j = 0; j < n; j++)
                {
                        cin >> temp;
                        p[i][j] = mallocPoint(i, j, temp);
                }
        }

        //设置每点的相邻
        for (i = 0; i < n; i++)
        {
                for (j = 0; j < n; j++)
                {
                        setv(p, p[i][j], n);
                }
        }

        b[0] = merge(p[x][y], 0);
       
}

void setv(Point*** p, Point *g, int n)
{
        int x, y;

        x = g->x;
        y = g->y;

        //有上
        if (g->x - 1 >= 0)
        {
                g->v.push_back(p[x - 1][y]);
        }
        if (g->y - 1 >= 0)
        {
                g->v.push_back(p[x][y - 1]);
        }
        if (g->x + 1 < n)
        {
                g->v.push_back(p[x + 1][y]);
        }
        if (g->y + 1 < n)
        {
                g->v.push_back(p[x][y + 1]);
        }
}

//输入点 合并该点周围的正权值点
//返回合并后的区域
Block* merge(Point* p, int id)
{
        //栈
        vector<Point*> s;
        Point* g;
        Block* b = mallocBlock(id);
        int i;

        s.push_back(p);
        while (!s.empty())
        {
                p = s.back();               
                b->v.push_back(p);        //将该点加入区域内
                b->p += p->p;        //更新区域积分
                p->p = 0;
                p->id = id;

                for (i = 0; i < p->v.size(); i++)
                {
                        g = p->v[i];
                        if (g->p >= 0 && g->p == -1)
                        {
                                s.push_back(g);
                        }
                }
        }
        return b;
}

最佳答案

月排行榜 / 总排行榜

人造人

2021-12-5 15:06:39

代码一堆的问题
核心问题就是你在C++中使用了malloc/free
哦不，你并没有用free，因为你不喜欢释放内存，去玩python、java吧
这类语言不需要你自己释放内存
这并不是说C++中不能用malloc/free，只是你要明白自己在做什么
并且只有new/delete无法满足你的需求的时候才使用malloc/free

帮你解决了内存泄漏的问题
现在来讨论一下这个程序的算法吧，要如何选择主角C的移动路径？

1. /*
   
2. #include"algorithm"
   
3. #include"iostream"
   
4. #include"vector"
   
5. */
   
6. #include <algorithm>
   
7. #include <iostream>
   
8. #include <vector>
   
9. #include <cstdint>
   
10. 
    
11. using namespace std;
    
12. 
    
13. typedef struct Point {
    
14.     int x;
    
15.     int y;
    
16.     int p;             //该点的积分
    
17.     int isto;          //单次寻路该节点是否已达
    
18.     int mp;            //在单次寻路中,能够到达该点的最大积分
    
19.     int temp;          //暂存积分值
    
20.     Point *h;          //最佳前驱节点
    
21.     Point *nh;         //当前路的前驱节点
    
22.     int id;            //标明该点位于第几个积分区域
    
23.     vector<Point *> v; //该容器存储周围的点
    
24. } Point;
    
25. 
    
26. typedef struct {
    
27.     int id;
    
28.     int p;             //该区域的积分
    
29. 
    
30.     // 哈？似乎无用？这代码不是你写的吗？
    
31.     int isto;          //似乎无用
    
32.     int mp;            //似乎无用
    
33.     int temp;          //似乎无用
    
34.     vector<Point *> v; //该区域内的边缘点
    
35. } Block;
    
36. 
    
37. //Point *mallocPoint(int x, int y, int p) {
    
38. Point *mallocPoint(int y, int x, int p) {
    
39.     Point *g;
    
40.     g = (Point *)malloc(sizeof(Point));
    
41.     g->x = x;
    
42.     g->y = y;
    
43.     g->p = p;
    
44.     g->isto = 0;
    
45.     g->mp = 0;
    
46.     g->temp = 0;
    
47.     g->h = nullptr;
    
48.     g->nh = nullptr;
    
49.     g->id = -1;
    
50. 
    
51.     // C++么，用new/delete多好？
    
52.     // 你非要用malloc/free
    
53.     // 这会发生什么呢？
    
54.     // 很简单，C++的对象没办法初始化
    
55.     // 就是说C++对象的构造函数没有被调用
    
56.     // 你写调用构造函数的代码了？
    
57.     // 你没有，malloc函数内部也没有这样的代码
    
58.     // 所以，下面补上这样的代码
    
59.     unsigned char *ptr = (unsigned char *)g + (uintptr_t)&((Point *)0)->v;
    
60.     new(ptr) vector<Point *>;
    
61.     return g;
    
62. }
    
63. 
    
64. Block *mallocBlock(int id) {
    
65.     Block *b;
    
66.     b = (Block *)malloc(sizeof(Block));
    
67.     b->id = id;
    
68.     b->p = 0;
    
69.     b->isto = 0;
    
70.     b->mp = 0;
    
71.     b->temp = 0;
    
72. 
    
73.     // 一样，下面调用v的构造函数
    
74.     unsigned char *ptr = (unsigned char *)b + (uintptr_t)&((Block *)0)->v;
    
75.     new(ptr) vector<Point *>;
    
76.     return b;
    
77. }
    
78. 
    
79. void function1(int n, int x, int y);
    
80. Block *merge(Point *p, int id);
    
81. void setv(Point ***p, Point *g, int n);
    
82. 
    
83. int main() {
    
84.     int n, x, y;
    
85. 
    
86.     // 为了检查是不是还有内存泄漏问题
    
87.     // 这里改一改
    
88.     /*
    
89.     while(cin >> n >> x >> y) {
    
90.         function1(n, x, y);
    
91.     }
    
92.     */
    
93.     cin >> n >> x >> y;
    
94.     function1(n, x, y);
    
95.     return 0;
    
96. }
    
97. 
    
98. void function1(int n, int x, int y) {
    
99.     Point ***p;
    
100.     vector<Block *> b;
     
101. 
     
102.     int temp;
     
103.     int i, j;
     
104.     //Point *maxP;
     
105. 
     
106.     x--;
     
107.     y--;
     
108. 
     
109.     p = (Point ***)malloc(sizeof(Point **) * n);
     
110.     p[0] = (Point **)malloc(sizeof(Point *) * n * n);
     
111.     for(i = 0; i < n; i++) {
     
112.         p[i] = p[0] + n * i;
     
113.     }
     
114. 
     
115.     //设置地图积分值
     
116.     //设置点未达
     
117.     for(i = 0; i < n; i++) {
     
118.         for(j = 0; j < n; j++) {
     
119.             cin >> temp;
     
120.             p[i][j] = mallocPoint(i, j, temp);
     
121.         }
     
122.     }
     
123. 
     
124.     //设置每点的相邻
     
125.     for(i = 0; i < n; i++) {
     
126.         for(j = 0; j < n; j++) {
     
127.             setv(p, p[i][j], n);
     
128.         }
     
129.     }
     
130. 
     
131.     // b[0] ?
     
132.     // b 是一个vector
     
133.     // vector到这个位置的时候，可以访问第0个元素？
     
134.     //b[0] = merge(p[x][y], 0);
     
135.     b.push_back(merge(p[x][y], 0));
     
136. 
     
137.     // 然后呢？然后就没有然后了？
     
138.     // 然后就释放掉vector，函数返回？
     
139.     // 同样，你又没写释放内存的代码
     
140.     // 现在补上
     
141.     b[0]->v.~vector();
     
142.     free(b[0]);
     
143. 
     
144.     // 申请了内存为什么不释放？
     
145.     // 不喜欢写释放内存的代码的话
     
146.     // 去玩java、python
     
147.     // C/C++ 并不适合你
     
148.     for(i = 0; i < n; i++) {
     
149.         for(j = 0; j < n; j++) {
     
150.             // 这里还得调用对象的析构函数
     
151.             // 因为free函数内部没有这样的代码
     
152.             // 你也没有写这样的代码
     
153.             // 这导致C++对象无法被析构
     
154.             // 所以说，在C++中你用什么malloc/free ？
     
155.             // 用new/delete多好？
     
156.             p[i][j]->v.~vector();
     
157.             free(p[i][j]);
     
158.         }
     
159.     }
     
160.     free(p[0]);
     
161.     free(p);
     
162. }
     
163. 
     
164. void setv(Point ***p, Point *g, int n) {
     
165.     int x, y;
     
166. 
     
167.     x = g->x;
     
168.     y = g->y;
     
169. 
     
170.     //有上
     
171.     if(g->x - 1 >= 0) {
     
172.         g->v.push_back(p[x - 1][y]);
     
173.     }
     
174.     if(g->y - 1 >= 0) {
     
175.         g->v.push_back(p[x][y - 1]);
     
176.     }
     
177.     if(g->x + 1 < n) {
     
178.         g->v.push_back(p[x + 1][y]);
     
179.     }
     
180.     if(g->y + 1 < n) {
     
181.         g->v.push_back(p[x][y + 1]);
     
182.     }
     
183. }
     
184. 
     
185. //输入点 合并该点周围的正权值点
     
186. //返回合并后的区域
     
187. Block *merge(Point *p, int id) {
     
188.     // 栈
     
189.     // 栈？这不vector么？
     
190.     // 栈不是stack么？
     
191.     vector<Point *> s;
     
192.     //Point *g;
     
193.     Block *b = mallocBlock(id);
     
194.     //int i;
     
195. 
     
196. #if 0
     
197.     s.push_back(p);
     
198.     while(!s.empty()) {
     
199.         // 这while里面都没有s.pop_back函数
     
200.         // s怎么可能为空？
     
201.         // 所以这里死循环了
     
202.         p = s.back();
     
203.         b->v.push_back(p); //将该点加入区域内
     
204.         b->p += p->p;      //更新区域积分
     
205.         p->p = 0;
     
206.         p->id = id;
     
207. 
     
208. #if 0
     
209.         for(i = 0; i < p->v.size(); i++) {
     
210.             //g = p->v[i];
     
211.             // 这里不知道你在做什么
     
212.             // 这里有一个警告
     
213.             // overlapping comparisons always evaluate to false
     
214.             /*
     
215.             if(g->p >= 0 && g->p == -1) {
     
216.                 s.push_back(g);
     
217.             }
     
218.             */
     
219.         }
     
220. #endif
     
221.     }
     
222. #endif
     
223.     return b;
     
224. }
     

复制代码

跳转到最佳答案楼层

人造人

题目？

梦竹风

人造人 发表于 2021-12-5 12:45
题目？

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

傻眼貓咪

看似容易，实则困难。一般如果不止一种解答的题目最困难（因为不通的路线相对也多），

以你的题目作为例子：
1.）要考量到路线可以重复（无限多个解法）
2.）上下左右可移动（至少 4 次方解法）

这是困难级别的题目，希望有哪位大神的代码可以让我学习学习。

一般都会以起点和终点作为参数，并以最优路线题解，但你的题目只给起点，就好象你问你的女朋友今天想吃什么，你女朋友回答随便一样道理

人造人

代码一堆的问题
核心问题就是你在C++中使用了malloc/free
哦不，你并没有用free，因为你不喜欢释放内存，去玩python、java吧
这类语言不需要你自己释放内存
这并不是说C++中不能用malloc/free，只是你要明白自己在做什么
并且只有new/delete无法满足你的需求的时候才使用malloc/free

帮你解决了内存泄漏的问题
现在来讨论一下这个程序的算法吧，要如何选择主角C的移动路径？

1. /*
   
2. #include"algorithm"
   
3. #include"iostream"
   
4. #include"vector"
   
5. */
   
6. #include <algorithm>
   
7. #include <iostream>
   
8. #include <vector>
   
9. #include <cstdint>
   
10. 
    
11. using namespace std;
    
12. 
    
13. typedef struct Point {
    
14.     int x;
    
15.     int y;
    
16.     int p;             //该点的积分
    
17.     int isto;          //单次寻路该节点是否已达
    
18.     int mp;            //在单次寻路中,能够到达该点的最大积分
    
19.     int temp;          //暂存积分值
    
20.     Point *h;          //最佳前驱节点
    
21.     Point *nh;         //当前路的前驱节点
    
22.     int id;            //标明该点位于第几个积分区域
    
23.     vector<Point *> v; //该容器存储周围的点
    
24. } Point;
    
25. 
    
26. typedef struct {
    
27.     int id;
    
28.     int p;             //该区域的积分
    
29. 
    
30.     // 哈？似乎无用？这代码不是你写的吗？
    
31.     int isto;          //似乎无用
    
32.     int mp;            //似乎无用
    
33.     int temp;          //似乎无用
    
34.     vector<Point *> v; //该区域内的边缘点
    
35. } Block;
    
36. 
    
37. //Point *mallocPoint(int x, int y, int p) {
    
38. Point *mallocPoint(int y, int x, int p) {
    
39.     Point *g;
    
40.     g = (Point *)malloc(sizeof(Point));
    
41.     g->x = x;
    
42.     g->y = y;
    
43.     g->p = p;
    
44.     g->isto = 0;
    
45.     g->mp = 0;
    
46.     g->temp = 0;
    
47.     g->h = nullptr;
    
48.     g->nh = nullptr;
    
49.     g->id = -1;
    
50. 
    
51.     // C++么，用new/delete多好？
    
52.     // 你非要用malloc/free
    
53.     // 这会发生什么呢？
    
54.     // 很简单，C++的对象没办法初始化
    
55.     // 就是说C++对象的构造函数没有被调用
    
56.     // 你写调用构造函数的代码了？
    
57.     // 你没有，malloc函数内部也没有这样的代码
    
58.     // 所以，下面补上这样的代码
    
59.     unsigned char *ptr = (unsigned char *)g + (uintptr_t)&((Point *)0)->v;
    
60.     new(ptr) vector<Point *>;
    
61.     return g;
    
62. }
    
63. 
    
64. Block *mallocBlock(int id) {
    
65.     Block *b;
    
66.     b = (Block *)malloc(sizeof(Block));
    
67.     b->id = id;
    
68.     b->p = 0;
    
69.     b->isto = 0;
    
70.     b->mp = 0;
    
71.     b->temp = 0;
    
72. 
    
73.     // 一样，下面调用v的构造函数
    
74.     unsigned char *ptr = (unsigned char *)b + (uintptr_t)&((Block *)0)->v;
    
75.     new(ptr) vector<Point *>;
    
76.     return b;
    
77. }
    
78. 
    
79. void function1(int n, int x, int y);
    
80. Block *merge(Point *p, int id);
    
81. void setv(Point ***p, Point *g, int n);
    
82. 
    
83. int main() {
    
84.     int n, x, y;
    
85. 
    
86.     // 为了检查是不是还有内存泄漏问题
    
87.     // 这里改一改
    
88.     /*
    
89.     while(cin >> n >> x >> y) {
    
90.         function1(n, x, y);
    
91.     }
    
92.     */
    
93.     cin >> n >> x >> y;
    
94.     function1(n, x, y);
    
95.     return 0;
    
96. }
    
97. 
    
98. void function1(int n, int x, int y) {
    
99.     Point ***p;
    
100.     vector<Block *> b;
     
101. 
     
102.     int temp;
     
103.     int i, j;
     
104.     //Point *maxP;
     
105. 
     
106.     x--;
     
107.     y--;
     
108. 
     
109.     p = (Point ***)malloc(sizeof(Point **) * n);
     
110.     p[0] = (Point **)malloc(sizeof(Point *) * n * n);
     
111.     for(i = 0; i < n; i++) {
     
112.         p[i] = p[0] + n * i;
     
113.     }
     
114. 
     
115.     //设置地图积分值
     
116.     //设置点未达
     
117.     for(i = 0; i < n; i++) {
     
118.         for(j = 0; j < n; j++) {
     
119.             cin >> temp;
     
120.             p[i][j] = mallocPoint(i, j, temp);
     
121.         }
     
122.     }
     
123. 
     
124.     //设置每点的相邻
     
125.     for(i = 0; i < n; i++) {
     
126.         for(j = 0; j < n; j++) {
     
127.             setv(p, p[i][j], n);
     
128.         }
     
129.     }
     
130. 
     
131.     // b[0] ?
     
132.     // b 是一个vector
     
133.     // vector到这个位置的时候，可以访问第0个元素？
     
134.     //b[0] = merge(p[x][y], 0);
     
135.     b.push_back(merge(p[x][y], 0));
     
136. 
     
137.     // 然后呢？然后就没有然后了？
     
138.     // 然后就释放掉vector，函数返回？
     
139.     // 同样，你又没写释放内存的代码
     
140.     // 现在补上
     
141.     b[0]->v.~vector();
     
142.     free(b[0]);
     
143. 
     
144.     // 申请了内存为什么不释放？
     
145.     // 不喜欢写释放内存的代码的话
     
146.     // 去玩java、python
     
147.     // C/C++ 并不适合你
     
148.     for(i = 0; i < n; i++) {
     
149.         for(j = 0; j < n; j++) {
     
150.             // 这里还得调用对象的析构函数
     
151.             // 因为free函数内部没有这样的代码
     
152.             // 你也没有写这样的代码
     
153.             // 这导致C++对象无法被析构
     
154.             // 所以说，在C++中你用什么malloc/free ？
     
155.             // 用new/delete多好？
     
156.             p[i][j]->v.~vector();
     
157.             free(p[i][j]);
     
158.         }
     
159.     }
     
160.     free(p[0]);
     
161.     free(p);
     
162. }
     
163. 
     
164. void setv(Point ***p, Point *g, int n) {
     
165.     int x, y;
     
166. 
     
167.     x = g->x;
     
168.     y = g->y;
     
169. 
     
170.     //有上
     
171.     if(g->x - 1 >= 0) {
     
172.         g->v.push_back(p[x - 1][y]);
     
173.     }
     
174.     if(g->y - 1 >= 0) {
     
175.         g->v.push_back(p[x][y - 1]);
     
176.     }
     
177.     if(g->x + 1 < n) {
     
178.         g->v.push_back(p[x + 1][y]);
     
179.     }
     
180.     if(g->y + 1 < n) {
     
181.         g->v.push_back(p[x][y + 1]);
     
182.     }
     
183. }
     
184. 
     
185. //输入点 合并该点周围的正权值点
     
186. //返回合并后的区域
     
187. Block *merge(Point *p, int id) {
     
188.     // 栈
     
189.     // 栈？这不vector么？
     
190.     // 栈不是stack么？
     
191.     vector<Point *> s;
     
192.     //Point *g;
     
193.     Block *b = mallocBlock(id);
     
194.     //int i;
     
195. 
     
196. #if 0
     
197.     s.push_back(p);
     
198.     while(!s.empty()) {
     
199.         // 这while里面都没有s.pop_back函数
     
200.         // s怎么可能为空？
     
201.         // 所以这里死循环了
     
202.         p = s.back();
     
203.         b->v.push_back(p); //将该点加入区域内
     
204.         b->p += p->p;      //更新区域积分
     
205.         p->p = 0;
     
206.         p->id = id;
     
207. 
     
208. #if 0
     
209.         for(i = 0; i < p->v.size(); i++) {
     
210.             //g = p->v[i];
     
211.             // 这里不知道你在做什么
     
212.             // 这里有一个警告
     
213.             // overlapping comparisons always evaluate to false
     
214.             /*
     
215.             if(g->p >= 0 && g->p == -1) {
     
216.                 s.push_back(g);
     
217.             }
     
218.             */
     
219.         }
     
220. #endif
     
221.     }
     
222. #endif
     
223.     return b;
     
224. }
     

复制代码

人造人

傻眼貓咪 发表于 2021-12-5 13:57
看似容易，实则困难。一般如果不止一种解答的题目最困难（因为不通的路线相对也多），

以你的题目作为例 ...

确实，这问题不简单
这题目需要不错的数学和算法知识
正好这两点我都不满足
完全想不出来要如何选择主角C的移动路径
^_^

梦竹风

人造人 发表于 2021-12-5 15:09
确实，这问题不简单
这题目需要不错的数学和算法知识
正好这两点我都不满足

其实看程序也猜的出来这题完全没做完所以整个过程看的会很莫名其妙
关于malloc 和 free 问题 其实在这道题以前我一直写的c    c++很少写
只不过这次我想用一下stl里的vector 而且也要蓝桥杯了 总不能在赛场上自己整个stack出来那太浪费时间了

关于用的时stack 却用了vector 这个问题 我也不知道该怎么回答 毕竟我好像也忘了为什么要用vector 不用stack  不过只用vector 应该也是可以实现 stack的功能

关于在merge 函数 while循环里没有pop  这个是我的问题 忘了 不过代码一直不能运行到那里 所以我也没发现到这个错误

内存泄漏问题 一直以来我们老师也是很强调 malloc 的空间需要 free  不过我刷oj时就懒得加 free 了 更别说这道题我都还没写完  不过这确实是我的坏习惯

人造人

梦竹风 发表于 2021-12-5 16:13
其实看程序也猜的出来这题完全没做完所以整个过程看的会很莫名其妙
关于malloc 和 free 问题 其实在这道 ...

嗯，来讨论一下如何选择主角C的移动路径吧

梦竹风

人造人 发表于 2021-12-5 15:09
确实，这问题不简单
这题目需要不错的数学和算法知识
正好这两点我都不满足

这道题我还是有一个初步的程序的  当然程序粗糙至极 也没有free  程序的输出也是错误的  在遇到n>=5 的情况直接就跑不出来了  以下是程序代码


#include"iostream"

#include"vector"
#include"algorithm"

using namespace std;


typedef struct _POINT
{
        int i;
        int j;
        int isto;        //单次寻路该节点是否已达
        int mp;        //在单次寻路中,能够到达该点的最大积分
        int temp;        //暂存积分值
        struct _POINT* h;        //最佳前驱节点
        struct _POINT* nh;        //当前路的前驱节点

        int p;        //该点的积分


}POINT;

int mymax = 0;        //用于存储单次寻路中整个地图最佳节点的权值,当该值需要更新时会更新该最佳路的节点的前驱节点（更新前驱节点这里是重点）
void function1(int n, int x, int y);
int up(POINT** p, int x, int y, int n);

void dfs(POINT** p, vector<POINT*> v, int n);
void dfs2(POINT** p, vector<POINT*> v, POINT* d, POINT* g, int n);
void setH(POINT* p);




int main()
{
        int n, x, y;
        while(cin >> n >> x >> y)
        {
                function1(n, x, y);
        }
       
}


void function1(int n, int x, int y)
{
        //vector<vector<POINT>>;
        POINT** p;

        int temp;
        int i, j;
        POINT* maxP;


        x--;
        y--;

        p = (POINT**)malloc(sizeof(POINT*) * n);
        p[0] = (POINT*)malloc(sizeof(POINT) * n * n);

        for (i = 0; i < n; i++)
        {
                p[i] = p[0] + i * n;
        }

        //设置地图积分值
        //设置点未达
        for (i = 0; i < n; i++)
        {
                for (j = 0; j < n; j++)
                {
                        cin >> temp;
                        p[i][j].p = temp;
                        p[i][j].isto = 0;       
                        p[i][j].i = i;
                        p[i][j].j = j;
                        p[i][j].mp = 0;
                        p[i][j].temp = 0;
                }
        }

        cout << up(p, x, y, n) << endl;

}

//更新地图
//返回最优点
int up(POINT **p, int x, int y, int n)
{
        vector<POINT*> v;
        POINT* g;
        POINT* d;
        int temp;
        POINT* maxP;
        int i, j;
        vector<POINT*> a;        //存储已达域

       

        v.push_back(&p[x][y]);
        temp = p[x][y].p;
        p[x][y].p = 0;
        p[x][y].h = NULL;
        p[x][y].nh = NULL;

        a.push_back(&p[x][y]);


        while (1)
        {
                mymax = 0;
                dfs(p, v, n);
                maxP = &p[0][0];
                for (i = 0; i < n; i++)
                {
                        for (j = 0; j < n; j++)
                        {
                                p[i][j].isto = 0;
                                if (p[i][j].mp > maxP->mp)
                                {
                                        maxP = &p[i][j];
                                }
                        }
                }
                if (maxP->mp <= 0)
                {
                        break;
                }
                temp += maxP->mp;
                while (maxP->h)
                {
                        maxP->mp = maxP->temp = maxP->p = 0;

                        maxP = maxP->h;

                }
        }
        return temp;
}


void dfs(POINT** p, vector<POINT*> v, int n)
{
        POINT* d, * g;
        int temp;
        g = v.back();

        //该点有上
        if (g->i != 0)
        {

                d = &p[g->i - 1][g->j];
                if (d->p)
                {
                        dfs2(p, v, d, g, n);
                }
               
        }

        //有左
        if (g->j != 0)
        {
                d = &p[g->i][g->j - 1];
                if (d->p)
                {
                        dfs2(p, v, d, g, n);
                }
        }

        //有下
        if (g->i < n - 1)
        {
                d = &p[g->i + 1][g->j];
                if (d->p)
                {
                        dfs2(p, v, d, g, n);
                }
        }

        //有右
        if (g->j < n - 1)
        {
                d = &p[g->i][g->j + 1];
                if (d->p)
                {
                        dfs2(p, v, d, g, n);
                }
        }
}
       


void dfs2(POINT** p, vector<POINT*> v, POINT* d, POINT *g, int n)
{
        int temp;
        if (find(v.begin(), v.end(), d) == v.end())
        {
                //该点不在栈里
                //现在的栈相当于一条路径，这里用于保证不会重复经过某一点以造成左右横跳死循环
                temp = g->temp + d->p;
                d->nh = g;

                if (!d->isto)
                {
                        //本次寻路中第一次到达这个节点 则需要更新该节点的最佳权值
                        d->isto = 1;
                        d->mp = temp;
                        d->temp = temp;
                        d->h = g;
                }
               
                else
                {
                        //不是第一次到达这个节点
                        //先更新本次积分值
                        d->temp = temp;
                        if (d->temp > d->mp)
                        {
                                //本次积分值大于该点的最佳权值，则更新该点的最佳权值
                                d->mp = d->temp;
                        }
                }

                if (temp > mymax)
                {
                        //若该点为当前已知最佳点
                        setH(d);
                        mymax = temp;
                       
                }
                v.push_back(d);
                dfs(p, v, n);
        }
}


//更新最佳前驱节点
void setH(POINT *p)
{
        while (p->nh)
        {
                p->h = p->nh;
                p = p->h;
        }
        return;
}

该程序自然是错的 不过大致的想法大概能从中体现
我个人觉得这道题难点应该就在于 如何设置dfs 这个函数 来减少运算量
比如遇到权值吓人的忧郁豆子 这种就应该不要去吃 这样就可以减少一部分运算量
还有一些其他的情况就慢慢想吧

梦竹风

人造人 发表于 2021-12-5 15:09
确实，这问题不简单
这题目需要不错的数学和算法知识
正好这两点我都不满足

哦 我好像想起来了 我用vector  是因为 有find 函数  stack好像没有 所以我用了vector  具体可以看我刚刚发的代码

梦竹风

梦竹风 发表于 2021-12-5 16:13
其实看程序也猜的出来这题完全没做完所以整个过程看的会很莫名其妙
关于malloc 和 free 问题 其实在这道 ...

弱弱的问一下  我粘贴过来的代码 怎么做成那种框框

人造人

梦竹风 发表于 2021-12-5 16:32
弱弱的问一下  我粘贴过来的代码 怎么做成那种框框

回复的时候有一个 <> 按钮

这个问题同样在我的知识范围之外，我不一定能帮你，我去找一找资料，研究研究

梦竹风

这个是我提交到平台的代码  原注释已经无了  有看不懂的操作 我可以解释

1. #include"iostream"
   
2. 
   
3. #include"vector"
   
4. #include"algorithm"
   
5. 
   
6. using namespace std;
   
7. 
   
8. 
   
9. typedef struct _POINT
   
10. {
    
11.         int i;
    
12.         int j;
    
13.         int isto;        //??????????????????????
    
14.         int mp;        //????????????,??????????????????????
    
15.         int temp;        //??????????
    
16.         struct _POINT* h;        //????????????
    
17.         struct _POINT* nh;        //????????????????
    
18. 
    
19.         int p;        //??????????
    
20. 
    
21. 
    
22. }POINT;
    
23. 
    
24. int mymax = 0;        //????????????????????????????????????????,????????????????????????????????????????????????????????????????????????
    
25. void function1(int n, int x, int y);
    
26. int up(POINT** p, int x, int y, int n);
    
27. 
    
28. void dfs(POINT** p, vector<POINT*> v, int n);
    
29. void dfs2(POINT** p, vector<POINT*> v, POINT* d, POINT* g, int n);
    
30. void setH(POINT* p);
    
31. 
    
32. 
    
33. 
    
34. 
    
35. int main()
    
36. {
    
37.         int n, x, y;
    
38.         while(cin >> n >> x >> y)
    
39.         {
    
40.                 function1(n, x, y);
    
41.         }
    
42.        
    
43. }
    
44. 
    
45. 
    
46. void function1(int n, int x, int y)
    
47. {
    
48. 
    
49.         POINT** p;
    
50. 
    
51.         int temp;
    
52.         int i, j;
    
53.         POINT* maxP;
    
54. 
    
55. 
    
56.         x--;
    
57.         y--;
    
58. 
    
59.         p = (POINT**)malloc(sizeof(POINT*) * n);
    
60.         p[0] = (POINT*)malloc(sizeof(POINT) * n * n);
    
61. 
    
62.         for (i = 0; i < n; i++)
    
63.         {
    
64.                 p[i] = p[0] + i * n;
    
65.         }
    
66. 
    
67.         //??????????????
    
68.         //??????????
    
69.         for (i = 0; i < n; i++)
    
70.         {
    
71.                 for (j = 0; j < n; j++)
    
72.                 {
    
73.                         cin >> temp;
    
74.                         p[i][j].p = temp;
    
75.                         p[i][j].isto = 0;       
    
76.                         p[i][j].i = i;
    
77.                         p[i][j].j = j;
    
78.                         p[i][j].mp = 0;
    
79.                         p[i][j].temp = 0;
    
80.                 }
    
81.         }
    
82. 
    
83.         cout << up(p, x, y, n) << endl;
    
84. 
    
85. }
    
86. 
    
87. //????????
    
88. //??????????
    
89. int up(POINT **p, int x, int y, int n)
    
90. {
    
91.         vector<POINT*> v;
    
92.         POINT* g;
    
93.         POINT* d;
    
94.         int temp;
    
95.         POINT* maxP;
    
96.         int i, j;
    
97.         vector<POINT*> a;        //??????????
    
98. 
    
99.        
    
100. 
     
101.         v.push_back(&p[x][y]);
     
102.         temp = p[x][y].p;
     
103.         p[x][y].p = 0;
     
104.         p[x][y].h = NULL;
     
105.         p[x][y].nh = NULL;
     
106. 
     
107.         a.push_back(&p[x][y]);
     
108. 
     
109. 
     
110.         while (1)
     
111.         {
     
112.                 mymax = 0;
     
113.                 dfs(p, v, n);
     
114.                 maxP = &p[0][0];
     
115.                 for (i = 0; i < n; i++)
     
116.                 {
     
117.                         for (j = 0; j < n; j++)
     
118.                         {
     
119.                                 p[i][j].isto = 0;
     
120.                                 if (p[i][j].mp > maxP->mp)
     
121.                                 {
     
122.                                         maxP = &p[i][j];
     
123.                                 }
     
124.                         }
     
125.                 }
     
126.                 if (maxP->mp <= 0)
     
127.                 {
     
128.                         break;
     
129.                 }
     
130.                 temp += maxP->mp;
     
131.                 while (maxP->h)
     
132.                 {
     
133.                         maxP->mp = maxP->temp = maxP->p = 0;
     
134. 
     
135.                         maxP = maxP->h;
     
136. 
     
137.                 }
     
138.         }
     
139.         return temp;
     
140. }
     
141. 
     
142. 
     
143. void dfs(POINT** p, vector<POINT*> v, int n)
     
144. {
     
145.         POINT* d, * g;
     
146.         int temp;
     
147.         g = v.back();
     
148. 
     
149.         //????????
     
150.         if (g->i != 0)
     
151.         {
     
152. 
     
153.                 d = &p[g->i - 1][g->j];
     
154.                 if (d->p)
     
155.                 {
     
156.                         dfs2(p, v, d, g, n);
     
157.                 }
     
158.                
     
159.         }
     
160. 
     
161.         //????
     
162.         if (g->j != 0)
     
163.         {
     
164.                 d = &p[g->i][g->j - 1];
     
165.                 if (d->p)
     
166.                 {
     
167.                         dfs2(p, v, d, g, n);
     
168.                 }
     
169.         }
     
170. 
     
171.         //????
     
172.         if (g->i < n - 1)
     
173.         {
     
174.                 d = &p[g->i + 1][g->j];
     
175.                 if (d->p)
     
176.                 {
     
177.                         dfs2(p, v, d, g, n);
     
178.                 }
     
179.         }
     
180. 
     
181.         //????
     
182.         if (g->j < n - 1)
     
183.         {
     
184.                 d = &p[g->i][g->j + 1];
     
185.                 if (d->p)
     
186.                 {
     
187.                         dfs2(p, v, d, g, n);
     
188.                 }
     
189.         }
     
190. }
     
191.        
     
192. 
     
193. 
     
194. void dfs2(POINT** p, vector<POINT*> v, POINT* d, POINT *g, int n)
     
195. {
     
196.         int temp;
     
197.         if (find(v.begin(), v.end(), d) == v.end())
     
198.         {
     
199.                 //????????????
     
200.                 //??????????????????????????????????????????????????????????????????????????
     
201.                 temp = g->temp + d->p;
     
202.                 d->nh = g;
     
203. 
     
204.                 if (!d->isto)
     
205.                 {
     
206.                         //???????????????????????????? ??????????????????????????
     
207.                         d->isto = 1;
     
208.                         d->mp = temp;
     
209.                         d->temp = temp;
     
210.                         d->h = g;
     
211.                 }
     
212.                
     
213.                 else
     
214.                 {
     
215.                         //??????????????????????
     
216.                         //????????????????
     
217.                         d->temp = temp;
     
218.                         if (d->temp > d->mp)
     
219.                         {
     
220.                                 //??????????????????????????????????????????????????
     
221.                                 d->mp = d->temp;
     
222.                         }
     
223.                 }
     
224. 
     
225.                 if (temp > mymax)
     
226.                 {
     
227.                         //??????????????????????
     
228.                         setH(d);
     
229.                         mymax = temp;
     
230.                        
     
231.                 }
     
232.                 v.push_back(d);
     
233.                 dfs(p, v, n);
     
234.         }
     
235. }
     
236. 
     
237. 
     
238. //????????????????
     
239. void setH(POINT *p)
     
240. {
     
241.         while (p->nh)
     
242.         {
     
243.                 p->h = p->nh;
     
244.                 p = p->h;
     
245.         }
     
246.         return;
     
247. }

复制代码

人造人

梦竹风 发表于 2021-12-5 16:37
这个是我提交到平台的代码  原注释已经无了  有看不懂的操作 我可以解释

我得先去研究研究自动寻路算法，我感觉我离这个问题还有一段距离，我感觉这个问题你指望不上我了

梦竹风

人造人 发表于 2021-12-5 16:42
我得先去研究研究自动寻路算法，我感觉我离这个问题还有一段距离，我感觉这个问题你指望不上我了

hhh没关系  其实我问的问题也只是我的程序为什么会报错  并不是具体问到这道问题  oj的题还是得自己刷的

梦竹风

傻眼貓咪 发表于 2021-12-5 13:57
看似容易，实则困难。一般如果不止一种解答的题目最困难（因为不通的路线相对也多），

以你的题目作为例 ...

刚刚吃饭回来路上有了个新想法
1 把所有点放入一个容器内 并按权值从小到大进行排序
2 删掉容器内权值最小的点（即扣的分最多） 判断此时图是否还保持连通性（有无因为去掉这个点而分成两块）
3 若此时图还保持连通性 则将该点放入 禁入域B
4 若此时图分成两块 返回2 （先略过该点）

5 若当前要删的点的权值为0（即起点）
则返回2 重新从头删点    不返回2的条件为 每次删点都会将图分成两块

6 当进行到这里时 基本可以保证 每删掉一个权值为负的点后 都会将图分成两块 此时计算第二块的权值 假设第二块的权值为 5 而删的点的权值为 -6 说明该点要不得  
7 重复以上步骤

以上就是这个新想法大概的步骤了
不过我无法确定这种操作是否时最优解  算是一种贪心算法  而且相比dfs搜索寻路 其时间复杂度应该较低
所以接下来我会尝试实现这个想法

欢迎讨论

梦竹风

人造人 发表于 2021-12-5 16:42
我得先去研究研究自动寻路算法，我感觉我离这个问题还有一段距离，我感觉这个问题你指望不上我了

刚刚吃饭回来路上有了个新想法
1 把所有点放入一个容器内 并按权值从小到大进行排序
2 删掉容器内权值最小的点（即扣的分最多） 判断此时图是否还保持连通性（有无因为去掉这个点而分成两块）
3 若此时图还保持连通性 则将该点放入 禁入域B
4 若此时图分成两块 返回2 （先略过该点）

5 若当前要删的点的权值为0（即起点）
则返回2 重新从头删点    不返回2的条件为 每次删点都会将图分成两块

6 当进行到这里时 基本可以保证 每删掉一个权值为负的点后 都会将图分成两块 此时计算第二块的权值 假设第二块的权值为 5 而删的点的权值为 -6 说明该点要不得  
7 重复以上步骤

以上就是这个新想法大概的步骤了
不过我无法确定这种操作是否时最优解  算是一种贪心算法  而且相比dfs搜索寻路 其时间复杂度应该较低
所以接下来我会尝试实现这个想法

欢迎讨论

傻眼貓咪

梦竹风 发表于 2021-12-5 19:21
刚刚吃饭回来路上有了个新想法
1 把所有点放入一个容器内 并按权值从小到大进行排序
2 删掉容器内权值 ...

你的第 2 点就已经出现问题了。

假设 n = 3
矩阵：
1     2       3
4     5   -100
6 -100  1000
扣最多的是 -100 有 2个，而且如果要接触 1000 必须先接触 -100 呢？（到底要不要减 100 呢？）

梦竹风

傻眼貓咪 发表于 2021-12-5 19:28
你的第 2 点就已经出现问题了。

假设 n = 3

当扣掉第一个100 后 明显图还未分块所以可以把这个点从容器中扔掉 当扣掉第二个100后 图分成了两块 此时第二块（这里的第二块是相对起点的  起点所在的那一块视为第一块）  若第二块为 1000  这是大于100 的 说明这个-100可以吃  若此时第二块是另外一块 很明显 21是小于100的 说明这个-100 是不可以吃的

傻眼貓咪

梦竹风 发表于 2021-12-5 19:32
当扣掉第一个100 后 明显图还未分块所以可以把这个点从容器中扔掉 当扣掉第二个100后 图分成了两块 此时 ...

如果矩阵是：

2  -1   1
-1  0  -1
1 - 1   2

起点为中间