2014-02-22 102 views
1

我目前正在參與騎士之旅項目。我的目標最終是使用回溯(通過實施堆棧)和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)或多個值來推送。我還需要創建一些我目前正在進行的綁定檢查(確保騎士不會移動到他去過的位置,並且不會離開棋盤)。最後,如果騎士確實卡住了,我需要使用我創建的彈出功能返回一步並嘗試繼續不同的移動。

我真的很感激任何幫助,更正,開始的地方或給出的其他建議!我很卡...

+0

我可以指出,你不需要一個動態增長鏈接列表呢?堆棧的最大尺寸是'N * N'(板上的平方總數)。因此,您可以使用單個數組和當前「堆疊」到其中的移動數量。 –

+0

@BenVoigt無論他選擇使用二維座標還是展平座標平面都無關緊要。他需要一種方法來存儲每次移動的座標(可能還有更多信息),以便他可以有效地回溯。 –

回答

0

讓我直說吧。您難以實現可以撤消移動的堆棧結構。

C++是不是我的強項,但在這裏就是我想接近堆棧

  1. 定義存儲的COORDS一個結構(也可能是回溯信息)
  2. 更新「節點」來存儲指針到你的新結構的一個實例。
  3. 更新'push()'定義以使用它。
  4. 更新'pop()'定義以返回它。
  5. 利潤...