我正在阅读 antti Lakesonen 的竞争性编程手册，我遇到了回溯以查找应用了一些优化的网格路径。简而言之，这里是跨网格的有效路径的规则：
0. Path search starts from top left cell and ends at bottom right cell.
1. A valid path has traversed all the cells of the grid once.
2. From current cell you can move right, left, top, bottom and only if the move doesn't leave the grid.
现在我已经编写了这段代码，它可以很好地dimension = 7与 time~400ms和 total的方形网格一起使用paths : 111712。我在这里有两个疑问：
-->dimension = 9即使是搜索中的第一个有效路径也需要花费大量时间来报告。我是陷入无限循环还是什么？
--> 网格路径搜索even number of dimension喜欢 2,4,6 都给answer 0。我尝试手动查找 2*2 和 4*4 网格的路径，但我发现不可能找到这样的路径，但我不知道如何正式或逻辑地证明即使尺寸方形网格也不能具有上述路径。
这是我的代码：
#include <bits/stdc++.h>
using namespace std;
#define LOG_PATH 1;
#define ARRAY_BASED_CONSTANT_GRID 1;
struct Cell {
int x,y;
};
const int HORIZONTAL_DIRECTION = 0, VERTICAL_DIRECTION = 1;
long long validPathCount, recursiveCallCount, visitedCellCount, currentDirection;
#ifdef ARRAY_BASED_CONSTANT_GRID
const int DIMENSION = 7;
bool grid[DIMENSION][DIMENSION];
#else
int DIMENSION;
vector<vector<bool>> grid;
#endif
/* *-*-*-*-*-*-*-*- UTILITY FUNCTIONS -*-*-*-*-*-*-*-*-*-*-*-*-*-* */
bool hasPathCompleted(Cell);
bool isPathValid();
void validPathCheckAndUpdate();
void setState(Cell);
void resetState(Cell);
void updateAndLogPathCounter();
void backtrackPathSearching(Cell);
void moveAlongTheGrid(Cell);
bool isOccupied(Cell);
bool canMoveRight(Cell);
bool canMoveLeft(Cell);
bool canMoveUp(Cell);
bool canMoveDown(Cell);
bool isRightBorder(Cell);
bool isLeftBorder(Cell);
bool isUpBorder(Cell);
bool isDownBorder(Cell);
Cell generateRight(Cell);
Cell generateLeft(Cell);
Cell generateUp(Cell);
Cell generateDown(Cell);
bool isThereHorizontalPartition();
bool isThereVerticalPartition();
void printGrid();
/* *-*-*-*-*-*-*-*- UTILITY FUNCTIONS -*-*-*-*-*-*-*-*-*-*-*-*-*-* */
Cell generateRight(Cell position) {
currentDirection = HORIZONTAL_DIRECTION;
return {position.x, position.y + 1};
}
Cell generateLeft(Cell position) {
currentDirection = HORIZONTAL_DIRECTION;
return {position.x, position.y - 1};
}
Cell generateUp(Cell position) {
currentDirection = VERTICAL_DIRECTION;
return {position.x - 1, position.y};
}
Cell generateDown(Cell position) {
currentDirection = VERTICAL_DIRECTION;
return {position.x + 1, position.y};
}
bool isRightBorder(Cell position) { return position.y == DIMENSION - 1; }
bool isLeftBorder(Cell position) { return position.y == 0; }
bool isUpBorder(Cell position) { return position.x == 0; }
bool isDownBorder(Cell position) { return position.x == DIMENSION - 1; }
bool isOccupied(Cell position) { return grid[position.x][position.y]; }
bool canMoveRight(Cell position) { return !isRightBorder(position) && !isOccupied(generateRight(position)); }
bool canMoveLeft(Cell position) { return !isLeftBorder(position) && !isOccupied(generateLeft(position)); }
bool canMoveUp(Cell position) { return !isUpBorder(position) && !isOccupied(generateUp(position)); }
bool canMoveDown(Cell position) { return !isDownBorder(position) && !isOccupied(generateDown(position)); }
bool hasPathCompleted(Cell position) { return position.x == DIMENSION - 1 && position.y == DIMENSION - 1; }
bool isPathValid() { return visitedCellCount == DIMENSION * DIMENSION; }
void validPathCheckAndUpdate() {
if (isPathValid()) { updateAndLogPathCounter(); }
}
void updateAndLogPathCounter() {
validPathCount++;
#ifdef LOG_PATH
cout << "\rFound " << validPathCount << " paths";
cout.flush();
#endif
}
void setState(Cell position) {
recursiveCallCount++;
visitedCellCount++;
grid[position.x][position.y] = true;
}
void resetState(Cell position) {
visitedCellCount--;
grid[position.x][position.y] = false;
}
void printGrid() {
cout << "-------------------------------" << endl;
for (int i = 0; i < DIMENSION; i++) {
for (int j = 0; j < DIMENSION; j++) {
cout << grid[i][j] << " ";
}
cout << endl;
}
}
void moveAlongTheGrid(Cell position) {
if (canMoveRight(position)) {
backtrackPathSearching(generateRight(position));
}
if (canMoveLeft(position)) {
backtrackPathSearching(generateLeft(position));
}
if (canMoveUp(position)) {
backtrackPathSearching(generateUp(position));
}
if (canMoveDown(position)) {
backtrackPathSearching(generateDown(position));
}
}
bool isThereHorizontalPartition(Cell position) {
if (currentDirection == VERTICAL_DIRECTION) {
if (!canMoveUp(position) && !canMoveDown(position)) {
if (canMoveLeft(position) && canMoveRight(position)) {
return true;
}
}
}
return false;
}
bool isThereVerticalPartition(Cell position) {
if (currentDirection == HORIZONTAL_DIRECTION) {
if (!canMoveLeft(position) && !canMoveRight(position)) {
if (canMoveUp(position) && canMoveDown(position)) {
return true;
}
}
}
return false;
}
// OPTIMIZATION : 4 > Direction awareness
// Optimization 3 followed border awareness but this concept can be generalized
// and we can make the grid aware of its direction
// If path can't go forward in current direction but either can turn into both cross axis path
// then there is partition
void backtrackPathSearching(Cell position) {
setState(position);
// printGrid();
// cout << "x : " << position.x << " y : " << position.y << endl;
// cout << "validPathCount : " << validPathCount << endl;
// string s;
// getline(cin, s);
if (hasPathCompleted(position)) {
validPathCheckAndUpdate();
}
else if (!isThereHorizontalPartition(position) && !isThereVerticalPartition(position)) {
moveAlongTheGrid(position);
}
resetState(position);
}
#ifndef ARRAY_BASED_CONSTANT_GRID
void inputFromUser() {
cout << "Give Dimension of box grid : ";
cin >> DIMENSION;
for (int i = 0; i < DIMENSION; i++) grid.push_back(vector<bool>(DIMENSION, false));
}
#endif
int main() {
#ifndef ARRAY_BASED_CONSTANT_GRID
inputFromUser();
#endif
validPathCount = recursiveCallCount = 0;
visitedCellCount = 1;
grid[0][0] = 1;
currentDirection = VERTICAL_DIRECTION;
backtrackPathSearching({1, 0});
cout << endl;
cout << "Paths : " << validPathCount * 2 << endl;
cout << "Calls : " << recursiveCallCount << endl;
return 0;
}
/*
Paths : 111712
Calls : 26790463
real 0m0.281s
user 0m0.281s
sys 0m0.000s
*/
只需评论ARRAY_BASED_CONSTANT_GRID以启用网格尺寸的用户输入。
有人可以帮我弄这个吗？提前致谢 ：）
PS：由于我的编码习惯，我不得不粘贴整个代码以使其合理。我知道在stackoverflow中只需要粘贴最少的代码，但在这里我不知道为了分析代码真正需要什么！