/* * 回溯法的典型问题 */ /* * 题目:设计一个函数,用来判断在一个矩形中是否存在一条包含 * 某字符串所有字符的路径。路径可以从矩阵中任意一格开始, * 每一步可以在矩阵中向左右上下移动一格。一个格子不能经过 * 多次。 */ #include<cstring> bool hasPathCore(const char* matrix, int rows, int cols, int row, int col, const char* str, int& pathLength, bool* visited) { if (str[pathLength] == '\0') { return true; } bool hasPath = false; if (row >= 0 && row < rows && col >= 0 && col < cols && matrix[row * cols + col] == str[pathLength] && !visited[row * cols + col]) { ++pathLength; visited[row * cols + col] = true; hasPath = hasPathCore(matrix, rows, cols, row, col-1, str, pathLength, visited) || hasPathCore(matrix, rows, cols, row, col + 1, str, pathLength, visited) || hasPathCore(matrix, rows, cols, row - 1, col, str, pathLength, visited) || hasPathCore(matrix, rows, cols, row + 1, col, str, pathLength, visited); if (!hasPath) { --pathLength; visited[row * cols + col] = false; } } return hasPath; } bool hasPath(char* matrix, int rows, int cols, char* str) { if (matrix == nullptr || rows < 1 || cols < 1 || str == nullptr) { return false; } bool* visited = new bool[rows * cols]; memset(visited, 0, rows*cols); int pathLength = 0; for (int row = 0; row < rows; ++row) { for (int col = 0; col < cols; ++col) { if (hasPathCore(matrix, rows, cols, row, col, str, pathLength, visited)) { delete[] visited; visited = nullptr; return true; } } } delete[] visited; visited = nullptr; return false; } /* * 题目:在地上有一个m行n列的方格。一个机器人从坐标(0,0)的格子开始移动, * 他每次可以向在左右上下移动一格,同一个格子不可以移动两次,也不能进入 * 行坐标和列坐标之和大于k的格子。 * 例如,当k为18时,机器人能够进入方格(35,37),因为3+5+3+7 = 18. 但它不能进入 * 方格(35, 38),因为3+5+3+8 = 19.请问该机器人能够到达多少个格子。 */ /* * 感觉上只需要遍历整个方格的下标,判断下标与k的关系就可以解答了。但是现在练习回溯法, * 就用回溯法的思想解答。 */ #include<cstring> int getDigitSum(int number) { int sum = 0; while (number > 0) { sum += number % 10; number /= 10; } return sum; } bool check(int threshold, int rows, int cols, int row, int col, bool* visited) { if (row >= 0 && row<rows && col >=0 && col <cols && getDigitSum(row) + getDigitSum(col) <= threshold) { return true; } return false; } int movingCountCore(int threshold, int rows, int cols, int row, int col, bool* visited) { int count = 0; if (check(threshold, rows, cols, row, col, visited)) { visited[row * cols + col] = true; count = 1 + movingCountCore(threshold, rows, cols, row + 1, col, visited) + movingCountCore(threshold, rows, cols, row - 1, col, visited) + movingCountCore(threshold, rows, cols, row, col + 1, visited) + movingCountCore(threshold, rows, cols, row, col - 1, visited); } return count; } int movingCount(int threshold, int rows, int cols) { if (threshold < 0 || rows <= 0 || cols <= 0) { return 0; } bool* visited = new bool[rows * cols]; memset(visited, 0, rows * cols); int count = movingCountCore(threshold, rows, cols, 0, 0, visited); delete[] visited; visited = nullptr; return count; }