使用兩次遍歷收集網格中的最大點 · GeeksForGeeks 中文系列教程

# 使用兩次遍歷收集網格中的最大點 > 原文： [https://www.geeksforgeeks.org/collect-maximum-points-in-a-grid-using-two-traversals/](https://www.geeksforgeeks.org/collect-maximum-points-in-a-grid-using-two-traversals/) 給定一個矩陣，其中每個單元格代表點。在以下條件下如何使用兩次遍歷來收集最大點？令給定網格的尺寸為 R xC。 1）第一個遍歷從左上角即（0，0）開始并應到達左下角即（R-1，0）。第二次遍歷從右上角開始，即（0，C-1），并且應該到達右下角，即（R-1，C-1）/ 2）從點（i，j），我們可以移至（i + 1，j + 1）或（i + 1，j-1）或（i + 1，j） 3）遍歷獲取特定單元格通過的所有點。如果一個遍歷已經收集了一個單元格的點，則另一遍歷如果再次通過該單元格則得不到任何點。 ``` Input : int arr[R][C] = {{3, 6, 8, 2}, {5, 2, 4, 3}, {1, 1, 20, 10}, {1, 1, 20, 10}, {1, 1, 20, 10}, }; Output: 73 Explanation : ![runninggrid](https://img.kancloud.cn/1a/e5/1ae57d0762e14ff66484c33561547169_286x254.png) First traversal collects total points of value 3 + 2 + 20 + 1 + 1 = 27 Second traversal collects total points of value 2 + 4 + 10 + 20 + 10 = 46. Total Points collected = 27 + 46 = 73. ``` **我們強烈建議您最小化瀏覽器，然后自己嘗試。** 這個想法是同時進行兩個遍歷。我們首先從（0，0）開始，第二次從（0，C-1）開始遍歷。需要注意的重要一點是，在任何特定步驟中，兩個遍歷都將在同一行中，而在所有可能的三步中，行數都會增加。令（x1，y1）和（x2，y2）分別表示第一和第二遍歷的當前位置。因此，由于 x1 和 x2 都向前移動，因此在任何時候 x1 都等于 x2，但是沿 y 可能會發生變化。由于 y 的變化可能以 3 種不變的方式發生（y），因此請向左（y – 1），向右（y + 1）。因此，y1，y2 之間總共有 9 種組合是可能的。基本案例之后的以下 9 個案例。 ``` Both traversals always move forward along x Base Cases: // If destinations reached if (x == R-1 && y1 == 0 && y2 == C-1) maxPoints(arr, x, y1, y2) = arr[x][y1] + arr[x][y2]; // If any of the two locations is invalid (going out of grid) if input is not valid maxPoints(arr, x, y1, y2) = -INF (minus infinite) // If both traversals are at same cell, then we count the value of cell // only once. If y1 and y2 are same result = arr[x][y1] Else result = arr[x][y1] + arr[x][y2] result += max { // Max of 9 cases maxPoints(arr, x+1, y1+1, y2), maxPoints(arr, x+1, y1+1, y2+1), maxPoints(arr, x+1, y1+1, y2-1), maxPoints(arr, x+1, y1-1, y2), maxPoints(arr, x+1, y1-1, y2+1), maxPoints(arr, x+1, y1-1, y2-1), maxPoints(arr, x+1, y1, y2), maxPoints(arr, x+1, y1, y2+1), maxPoints(arr, x+1, y1, y2-1) } ``` 上面的遞歸解決方案有很多子問題，這些子問題一次又一次地得到解決。因此，我們可以使用動態編程更有效地解決上述問題。以下是[記憶](https://www.geeksforgeeks.org/dynamic-programming-set-1/)（在動態編程中記憶可替代基于表的迭代解決方案）。在下面的實現中，我們使用備忘錄表“ mem”來跟蹤已經解決的問題。 ## C++ ```cpp // A Memoization based program to find maximum collection // using two traversals of a grid #include<bits/stdc++.h> using namespace std; #define R 5 #define C 4 // checks whether a given input is valid or not bool isValid(int x, int y1, int y2) { ????return (x >= 0 && x < R && y1 >=0 && ????????????y1 < C && y2 >=0 && y2 < C); } // Driver function to collect max value int getMaxUtil(int arr[R][C], int mem[R][C][C], int x, int y1, int y2) { ????/*---------- BASE CASES -----------*/ ????// if P1 or P2 is at an invalid cell ????if (!isValid(x, y1, y2)) return INT_MIN; ????// if both traversals reach their destinations ????if (x == R-1 && y1 == 0 && y2 == C-1) ???????return (y1 == y2)? arr[x][y1]: arr[x][y1] + arr[x][y2]; ????// If both traversals are at last row but not at their destination ????if (x == R-1) return INT_MIN; ????// If subproblem is already solved ????if (mem[x][y1][y2] != -1) return mem[x][y1][y2]; ????// Initialize answer for this subproblem ????int ans = INT_MIN; ????// this variable is used to store gain of current cell(s) ????int temp = (y1 == y2)? arr[x][y1]: arr[x][y1] + arr[x][y2]; ????/* Recur for all possible cases, then store and return the ???????one with max value */ ????ans = max(ans, temp + getMaxUtil(arr, mem, x+1, y1, y2-1)); ????ans = max(ans, temp + getMaxUtil(arr, mem, x+1, y1, y2+1)); ????ans = max(ans, temp + getMaxUtil(arr, mem, x+1, y1, y2)); ????ans = max(ans, temp + getMaxUtil(arr, mem, x+1, y1-1, y2)); ????ans = max(ans, temp + getMaxUtil(arr, mem, x+1, y1-1, y2-1)); ????ans = max(ans, temp + getMaxUtil(arr, mem, x+1, y1-1, y2+1)); ????ans = max(ans, temp + getMaxUtil(arr, mem, x+1, y1+1, y2)); ????ans = max(ans, temp + getMaxUtil(arr, mem, x+1, y1+1, y2-1)); ????ans = max(ans, temp + getMaxUtil(arr, mem, x+1, y1+1, y2+1)); ????return (mem[x][y1][y2] = ans); } // This is mainly a wrapper over recursive function getMaxUtil(). // This function creates a table for memoization and calls // getMaxUtil() int geMaxCollection(int arr[R][C]) { ????// Create a memoization table and initialize all entries as -1 ????int mem[R][C][C]; ????memset(mem, -1, sizeof(mem)); ????// Calculation maximum value using memoization based function ????// getMaxUtil() ????return getMaxUtil(arr, mem, 0, 0, C-1); } // Driver program to test above functions int main() { ????int arr[R][C] = {{3, 6, 8, 2}, ?????????????????????{5, 2, 4, 3}, ?????????????????????{1, 1, 20, 10}, ?????????????????????{1, 1, 20, 10}, ?????????????????????{1, 1, 20, 10}, ????????????????????}; ????cout << "Maximum collection is " << geMaxCollection(arr); ????return 0; } ```