C++騎士遊歷問題(馬踏棋盤)解析
騎士遊歷問題:在國際棋盤上使一個騎士遍歷所有的格子一遍且僅一遍,對於任意給定的頂點,輸出一條符合上述要求的路徑
解題思路:
這是一道經典的遍歷問題(DFS),由於題目要求遍歷全部,那麼肯定要做標記,因此立馬想到DFS深度優先算法。具體思路如下:
①瞭解國際象棋以及國際象棋騎士的走法
國際象棋和中國象棋,大同小異,畢竟中國象棋是老祖先。國際象棋棋子放在格子中,中國象棋放在點上,且國際象棋有64個格子。國際象棋的騎士和中國象棋的馬功能相當,都可以走八個方位。走法是走“日”字,或英文字母大寫的“L”形:即先向左(或右)走1格,再向上(或下)走2格;或先向左(或右)走2格,再向上(或下)走1格。與中國象棋的馬不同,國際象棋的馬可以跳過路上的其他棋子,不受拐腳的限制。
解題需要我們可以把格子抽象成一個點,那麼國際象棋的騎士走法就是一個日字。
②設置標記
初始化數組,讓每個元素初始化為0,並且初始化一個記錄騎士遍歷次數的cal也為0
int cal = 0; //統計走的順序 //初始化為0 int chress[8][8] = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 };
③判斷是否超界和是否被訪問
bool ifOut(int x, int y) //判斷是否出界 { if (x >= 0 && x <= 7 && y >= 0 && y <= 7) return false; else return true; } bool ifVisited(int x, int y) //判斷是否被訪問 { if (chress[x][y] != 0) return true; else return false; }
④遞歸主體
void dfs(int x,int y) { if (cal == 64) //如果遍歷完則退出棋盤一共64個位置 return; if (!ifVisited(x, y) && !ifOut(x, y)) //如果沒有被訪問且沒有出界 則訪問 { cal++; chress[x][y] = cal; //做標記 dfs(x + 2, y + 1); //騎士走法有八個方位,故八個 方位都遍歷 dfs(x - 2, y - 1); //八個遞歸的順序可以改,順序不一樣,結果不一樣 dfs(x + 2, y - 1); dfs(x - 2, y + 1); dfs(x - 1, y - 2); dfs(x + 1, y - 2); dfs(x + 1, y + 2); dfs(x - 1, y + 2); return; } else //else其中包括已經被訪問瞭,和沒有被訪問且在界外的 return; }
⑤總代碼如下(編譯器vs2013)
#include"stdafx.h" #include<iostream> #include<iomanip> using namespace std; int cal = 0; //統計走的順序 //棋盤初始化為0做標記 int chress[8][8] = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }; bool ifOut(int x, int y) //判斷是否出界 { if (x >= 0 && x <= 7 && y >= 0 && y <= 7) return false; else return true; } bool ifVisited(int x, int y) //判斷是否已經被訪問 { if (chress[x][y] != 0) return true; else return false; } void dfs(int x,int y) { if (cal == 64) //如果遍歷完則退出棋盤一共64個位置 return; if (!ifVisited(x, y) && !ifOut(x, y)) //如果沒有被訪問且沒有出界 則訪問 { cal++; chress[x][y] = cal; //做標記 dfs(x + 2, y + 1); //騎士走法有八個方位,故八個 方位都遍歷 dfs(x - 2, y - 1); //八個遞歸的順序可以改,順序不一樣,結果不一樣 dfs(x + 2, y - 1); dfs(x - 2, y + 1); dfs(x - 1, y - 2); dfs(x + 1, y - 2); dfs(x + 1, y + 2); dfs(x - 1, y + 2); return; } else //出界瞭則退出return return; } int main() { int x, y; cout << "請輸入騎士初始的位置:"; while (1) { cin >> x >> y; //輸入坐標 if (x > 7 || x<0 || y> 7 || y < 0) cout << "初始位置輸入錯誤請重新輸入" << endl; else break; } dfs(x,y); for (int i = 0; i < 8; i++) //輸出打印測試 { for (int j = 0; j < 8; j++) cout << setw(2)<<chress[i][j]<<" "; cout << endl; } return 0; }
⑥測試截圖:
以上就是本文的全部內容,希望對大傢的學習有所幫助,也希望大傢多多支持WalkonNet。