我目前正在参与骑士之旅项目。我的目标最终是使用回溯(通过实施堆栈)和Warnsdorff的启发式创建此项目。我不允许使用任何已经创建了堆栈函数的库,例如push和pop。我也不允许使用递归来解决问题。说到这里,我现在很困难,我的下一个重要里程碑就是只用回溯来解决问题。骑士之旅将阵列传递给链表和更多
我根本不会去糖衣,但现在我的代码是一团糟。我几乎创建了所有需要的工具来使程序运行,但现在我只需要将所有部分放在一起。
以下是我的代码:
#include<iostream>
using namespace std;
class linkedList{
struct node
{
int data;
node *next;
};
node *top;
public:
linkedList()
{
top = NULL;
}
void push(int coordinates)
{
node *p = new node;
p -> data = coordinates;
p -> next = top;
top = p;
}
int pop()
{
node *temp = top;
top = temp -> next;
return temp -> data;
}
int display()
{
cout<<"\n"<< top -> data;
top = top-> next;
}
};
// Linked List ================================================
class Board{
public:
int next;
int status[8][8];
Board();
void print();
};
Board::Board(){
for(int i=0; i<8; i++){
for(int j=0; j<8; j++){
status[i][j] = -1;
}
}
}//constructor
void Board::print(){
for (int j=0; j<8; j++){
for(int i=0; i<8;i++){
cout << status[i][j] << " ";
}
cout << endl << endl;
}
}
//BOARD========================================================
class Knight {
private:
public:
int vertical[8] = {2,-2,1,-1,2,-2,1,-1}; // possible knight moves x coordinate
int horizontal[8] = {1,1,2,2,-1,-1,-2,-2}; // possible knight move y coordinate
int counter;
int currentPos[2];
Knight();
};
Knight::Knight(){
currentPos[0] = 7; // x-coordiante
currentPos[1] = 7; // y-coordinate
counter = 0;
}//constructor
/* Use this later
int Knight::changePos(int i,int j){
Knight::currentPos[0] = (Knight::currentPos[0] + i);
Knight::currentPos[1] = (Knight::currentPos[1] + j);
counter++;
return counter;
*/
int main(){
Board b;
Knight k;
b.status[k.currentPos[0]][k.currentPos[1]] = k.counter;
b.print();
linkedList obj;
int coordinates;
}
所以我在这一点上的想法是做到以下几点:
创建一个循环,将改变骑士的当前位置使用水平和垂直阵列(骑士可能的移动)。一旦位置发生变化,计数器将增加,-1将被当前计数器值替换。当骑士被移动时,新坐标的信息需要使用我创建的推送函数传递给链表。为了做到这一点,我需要找出一种方法来传递数组(x,y)或多个值来推送。我还需要创建一些我目前正在进行的绑定检查(确保骑士不会移动到他去过的位置,并且不会离开棋盘)。最后,如果骑士确实卡住了,我需要使用我创建的弹出功能返回一步并尝试继续不同的移动。
我真的很感激任何帮助,更正,开始的地方或给出的其他建议!我很卡...
我可以指出,你不需要一个动态增长链接列表呢?堆栈的最大尺寸是'N * N'(板上的平方总数)。因此,您可以使用单个数组和当前“堆叠”到其中的移动数量。 –
@BenVoigt无论他选择使用二维坐标还是展平坐标平面都无关紧要。他需要一种方法来存储每次移动的坐标(可能还有更多信息),以便他可以有效地回溯。 –