使用堆栈的骑士之旅C++

Question

我目前正在使用stack在C 的骑士旅游棋盘游戏中工作。我遇到一个奇怪的循环，该循环不会结束程序。有人可以帮助我使用代码吗？

#include <iostream>
#include <stack>
#include <map>
#include <cstdlib>
using namespace std;
struct whereIam
{
    int row, col;
};
struct L_shape_pattern
{
    int Lrow[8]={1,1,2,2,-1,-1,-2,-2};
    int Lcol[8]={2,-2,1,-1,2,-2,1,-1};

};
bool check_if_valid(int row, int col)
{
   if ((row >= 0 && col >= 0) && (row < 8 && col < 8))
   {
//       cout << "here in valid " <<endl;
              return true ;
   }
   else
       return false;
}
bool check_empty(bool board[8][8], whereIam position)
{
//   if (board[position.row][position.col] == false)
//       return false;
//   else
//       return true;
   if (board[position.row][position.col] == true)
   {
//       cout << "here in check empty" <<endl;
       return true;
   }
   else
       return false;
}
bool isReady(whereIam &position,bool board[8][8])
{
//    cout << "here" << endl;
    int ready = 0;
    for (int i = 0 ; i < 8 ; i ++)
    {
        for (int j = 0 ; j < 8 ; j++)
        {
            if(board[i][j] == false)
            {
                ready += 1;
            }
        }
    }
    cout << "ready: " <<ready << endl;
    if (ready == 64)
    {
        cout << "done" << endl;
        return true;
    }
    else
        return false;
}
void findspot(whereIam &position,bool board[8][8], stack<whereIam> &sequence)
{
    L_shape_pattern Lshape;
//    stack<whereIam> initial;
    stack<int> counter;

        for (int j = 0 ; j< 9 ;j++)
        {
            //nothing is assign here
            if (check_if_valid(position.row+Lshape.Lrow[j],position.col+Lshape.Lcol[j]) /*&& check_empty(board,position)*/)
            {
//                cout << "here in valid in spot " <<endl;
                whereIam hello;
                hello.row = position.row+Lshape.Lrow[j];
                hello.col = position.col+Lshape.Lcol[j];
//                cout << hello.row << " " << hello.col << endl;
                if (check_empty(board,hello))
                {
//                    cout << "here in empty" <<endl;
//                    int possible_row = position.row+Lshape.Lrow[j];
//                    int possible_col = position.col+Lshape.Lcol[j];
//                    position.row = possible_row;
//                    position.col = possible_col;
                    position.row = hello.row;
                    position.col = hello.col;
                    sequence.push(position);
//                    initial.push(position);
//                    cout << position.row << " " << position.col << endl;
                    counter.push(j);
                    board[position.row][position.col] = false;
                    j = -1;
                    if (isReady(position,board) == true)
                    {
                        cout << "in if ready" << endl;
                        exit(0);
                    }


                }

            }
            if (j == 8 )
            {
//                cout << "here in j = 8" <<endl;
                board[position.row][position.col] = true;
//                cout << " pop board " << position.row <<" " << position.col << endl;
                sequence.pop();
                position = sequence.top();
                // increment to the position where it need to be backtracking and it increment by one
                 j = counter.top();
                counter.pop();
                if (isReady(position,board) == true)
                {
                    cout << "in if ready" << endl;
                    exit(0);
                }
            }


        }

}
//bool movetheKnight(whereIam &position,bool board[8][8], stack<whereIam> &sequence)
//{
//}
void open_all_spot( bool board[8][8])
{
    for (int i = 0 ; i< 8 ; i++)
        for (int j= 0 ; j <8 ; j++)
        {
            board[i][j] = true;
        }
}
int main()
{
    bool board[8][8];
    open_all_spot(board);

    whereIam position;
    stack<whereIam> sequence;
    cout << "Enter the initial position" << endl;
    cout << "row : " ;
    cin >> position.row;
    cout << "column:";
    cin >> position.col;
    sequence.push(position);
    //assign the initial position to be occupied already
    board[position.row][position.col] = false;
    findspot(position,board,sequence);
    cout << "here end all" << endl;
    return 0;
}

我创建的一些部分是为了调试并查看每个功能的工作原理，因此请忽略这些部分。循环总是在继续，似乎根本没有结束。我试图跟踪堆栈中的数据，但对我来说确实很合理。

任何帮助将不胜感激。

Answer 1

查看代码的这一部分时：

for ( int j = 0; j < 9; j++ ) {
    if ( check_if_valid(position.row+Lshape.Lrow[j],position.col+Lshape.Lcol[j]) /*&& check_empty(board,position)*/) {
        // code...
        if ( checkEmpty( board, hello ) {
            // code...
            j = -1;
            if ( isReady(position, board) == true ) { // == true not needed
                // code...
            }
        }
    }
    if ( j == 8 ) {
        // code...
        j = counter.top()
        // code...
        if ( isReady(position, board) == true ) { // == true not needed
            // code...
        }
    }
} // for loop

考虑1 ^st 在条件返回时嵌套在for循环中的情况。您将j更改为-1。

在2 ^nd 中再次在for循环中的语句(如果j==8(中，您再次将j更改为counter.top()。

这种行为将导致for循环的无限递归。这是一个简单的例子：

#include <iostream>
#include <iomanip>
int main() {
    int counter = 0;
    for ( int i = 0; i < 5; i++ ) {
        if ( i == 4 ) {
            i = 0;
        }
        ++counter;
        std::cout << "Count the recursion: " 
                  << std::setw( 2 ) << counter << " " << i << 'n';
        // just to stop the recursion
        if ( counter == 10 ) break;
    }
    std::cout << "nPress any key and enter to quit.n";
    std::cin.get();
    return 0;
}

上面没有上次if语句的上述程序将模拟您程序中正在发生的情况。我只包括在内，以停止循环以显示输出的进展。

我不知道您是否故意想要无限的循环递归；但是，如果您需要在调试器中检查您的计数器变量，以确保它们与执行退出循环停止递归所涉及的语句所需的值匹配。就像我在上面的小例子中所示的那样；没有计数器的条件等于10。循环将永远继续下去。

作为旁注，如果您打算有一个无限的循环；通常最好以这种方式构建它们，以便您打算做什么更清楚。

int counter = 0;
for ( ; ; ) {
    ++counter;
    // do some work;
   if ( counter == exit condition )  break;
}

或

int counter = 0;
for ( ; ; ) {
    // do some work;
    if work above is valid
       increment counter
    else
       break;
}

或者您可以使用way循环

counter = some value
while ( true ) {
   check counter for condition;
   do some work
   increment or set counter;
}