采花生：寻找最大花生果并优化路径算法

{"title":"采花生：寻找最大花生果并优化路径算法","description":"本题描述了在一个花生田中寻找结花生果最多的一株花生植株，并从起点到该植株进行采摘的算法。算法通过两层循环遍历花生田，找到花生果最多的植株，然后按照先向南后向东的路线顺序进行采摘，最终输出摘取的花生果总数。","keywords":"采花生, 算法, 路径优化, 最短路径, 贪心算法, 时间复杂度, 空间复杂度, C++","content":"在参加“采花生”这个项目比赛时，考官会出示一块n行、m列的花生田，一共种了nm株花生苗，每株花生植株下都结了一定数量的花生果，选手一开始站在第1行，第1列的位置，要求用最短的时间找到结花生果最多的一株花生植株（数据保证花生果最多的植株只有一株），然后按先向南（下）走，再向东（右）的路线顺序去采摘它的花生果，沿路经过的其他花生植株下面的花生果也要一并摘下来，但不允许采摘没有路过的花生植株，否则依犯规出局处理。问这个选手一共可以采摘多少粒花生果？\n输入：\n第1行：两个整数nm(1<n,m<=100),表示花生田一共有n行m列\n第2.n+1行：每行m个空格隔开的整数，第i+1行的第j个整数Pij(0<=Pij<=700)表示花生田里植株(i,j)下花生的数目，0表示该植株下没有花生。\n输出：\n一行，一个整数，表示选手一共摘到的花生果数目。\n样例输入：\n5 6\n5 7 4 5 1 13\n9 6 3 2 8 7\n10 14 0 1 9 4\n4 6 9 18 25 0\n3 1 2 9 0 2\n样例输出：\n86\n要求：\n时间限制：1.0Sec\n内存限制：128MB\n用C++，尽量降低时间复杂度，确保答案正确\n内容：思路：\n首先，我们需要找到结花生果最多的一株花生植株。可以使用两层循环遍历花生田中的每株花生植株，记录下结花生果最多的植株的位置。\n\n然后，我们按照题目要求，从第1行第1列的位置开始，先向南（下）走，再向东（右）走，沿路经过的其他花生植株下面的花生果也要一并摘下来。\n我们可以使用两个变量来记录当前位置的行数和列数，然后按照题目要求进行移动，直到到达结花生果最多的植株的位置。\n\n在移动的过程中，我们可以使用一个变量来记录已经摘取的花生果的总数，每经过一个花生植株，就将该植株下的花生果数目加到总数中。\n\n最后，输出已经摘取的花生果的总数。\n\n代码实现如下：\ncpp\n#include <iostream>\n#include <vector>\n\nusing namespace std;\n\nint main() {\n int n, m;\n cin >> n >> m;\n\n vector<vector<int>> field(n, vector<int>(m));\n for (int i = 0; i < n; i++) {\n for (int j = 0; j < m; j++) {\n cin >> field[i][j];\n }\n }\n\n int maxRow = 0, maxCol = 0;\n int maxCount = field[0][0];\n\n for (int i = 0; i < n; i++) {\n for (int j = 0; j < m; j++) {\n if (field[i][j] > maxCount) {\n maxCount = field[i][j];\n maxRow = i;\n maxCol = j;\n }\n }\n }\n\n int count = 0;\n int row = 0, col = 0;\n\n while (row != maxRow) {\n count += field[row][col];\n row++;\n }\n\n while (col != maxCol) {\n count += field[row][col];\n col++;\n }\n\n count += field[row][col];\n\n cout << count << endl;\n\n return 0;\n}\n\n\n复杂度分析：\n遍历花生田中的所有花生植株的时间复杂度为O(nm)。\n移动到结花生果最多的植株的位置的时间复杂度为O(n+m)。\n因此，整体的时间复杂度为O(nm)。\n\n空间复杂度为O(nm)，用于存储花生田的信息。