c++ - バックトラッキングを使用して正方形グリッドへのパスを見つけるこのコードは正しいですか?

Question

私は、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これで、所要時間~400msと合計の正方形グリッドで正常に機能するこのコードを作成しましたpaths : 111712。ここに 2 つのクエリがあります。

-->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 では最小限の必要なコードのみを貼り付ける必要があることはわかっていますが、ここでは、コードを分析するために本当に必要なものがわかりません!

c++ - バックトラッキングを使用して正方形グリッドへのパスを見つけるこのコードは正しいですか?

0 に答える 0

Related

Reference