# 在死胡同之前收集最多硬幣 > 原文： [https://www.geeksforgeeks.org/collect-maximum-coins-before-hitting-a-dead-end/](https://www.geeksforgeeks.org/collect-maximum-coins-before-hitting-a-dead-end/) 給定一個字符矩陣，其中每個單元格都具有以下值之一。 ``` 'C' --> This cell has coin '#' --> This cell is a blocking cell. We can not go anywhere from this. 'E' --> This cell is empty. We don't get a coin, but we can move from here. ``` 初始位置是單元格（0，0），初始方向是正確的。 以下是跨單元移動的規則。 如果 face 是 Right，那么我們可以移到下面的單元格 1. 向前移動一步，即單元格（i，j + 1），方向保持正確。 2. 向下移動一步，然后向左移動，即單元格（i + 1，j），方向變為左。 如果臉是左，那么我們可以移動到下面的單元格 1. 向前移動一步，即單元格（i，j-1），方向保持不變。 2. 向下移動一步并面向右，即單元格（i + 1，j），方向變為正確。 最終位置可以在任何地方，最終方向也可以是任何東西。 目標是收集最多的硬幣。 **示例**： [](https://media.geeksforgeeks.org/wp-content/cdn-uploads/example.png) **我們強烈建議您最小化瀏覽器，然后自己嘗試。** 可以遞歸定義上述問題，如下所示： ``` maxCoins(i, j, d): Maximum number of coins that can be collected if we begin at cell (i, j) and direction d. d can be either 0 (left) or 1 (right) // If this is a blocking cell, return 0\. isValid() checks // if i and j are valid row and column indexes. If (arr[i][j] == '#' or isValid(i, j) == false) return 0 // Initialize result If (arr[i][j] == 'C') result = 1; Else result = 0; If (d == 0) // Left direction return result + max(maxCoins(i+1, j, 1), // Down maxCoins(i, j-1, 0)); // Ahead in left If (d == 1) // Right direction return result + max(maxCoins(i+1, j, 1), // Down maxCoins(i, j+1, 0)); // Ahead in right ``` 下面是上述遞歸算法的 C++ 實現。 ## C++ ```cpp // A Naive Recursive C++ program to find maximum number of coins // that can be collected before hitting a dead end #include<bits/stdc++.h> using namespace std; #define R 5 #define C 5 // to check whether current cell is out of the grid or not bool isValid(int i, int j) { ????return (i >=0 && i < R && j >=0 && j < C); } // dir = 0 for left, dir = 1 for facing right.? This function returns // number of maximum coins that can be collected starting from (i, j). int maxCoinsRec(char arr[R][C],? int i, int j, int dir) { ????// If this is a invalid cell or if cell is a blocking cell ????if (isValid(i,j) == false || arr[i][j] == '#') ????????return 0; ????// Check if this cell contains the coin 'C' or if its empty 'E'. ????int result = (arr[i][j] == 'C')? 1: 0; ????// Get the maximum of two cases when you are facing right in this cell ????if (dir == 1) // Direction is right ???????return result + max(maxCoinsRec(arr, i+1, j, 0),???? // Down ?????????????????????????????maxCoinsRec(arr, i, j+1, 1));? // Ahead in right ????// Direction is left ????// Get the maximum of two cases when you are facing left in this cell ?????return? result + max(maxCoinsRec(arr, i+1, j, 1),??? // Down ???????????????????????????maxCoinsRec(arr, i, j-1, 0));? // Ahead in left } // Driver program to test above function int main() { ????char arr[R][C] = { {'E', 'C', 'C', 'C', 'C'}, ???????????????????????{'C', '#', 'C', '#', 'E'}, ???????????????????????{'#', 'C', 'C', '#', 'C'}, ???????????????????????{'C', 'E', 'E', 'C', 'E'}, ???????????????????????{'C', 'E', '#', 'C', 'E'} ?????????????????????}; ???// As per the question initial cell is (0, 0) and direction is ????// right ????cout << "Maximum number of collected coins is " ?????????<< maxCoinsRec(arr, 0, 0, 1); ????return 0; } ```