C++騎士游歷問(wèn)題(馬踏棋盤(pán))解析
更新時(shí)間：2022年02月15日 12:18:13 作者：不禿頭的小李同學(xué)
這篇文章主要為大家詳細(xì)介紹了C++騎士游歷問(wèn)題的解答思路，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下
騎士游歷問(wèn)題：在國(guó)際棋盤(pán)上使一個(gè)騎士遍歷所有的格子一遍且僅一遍，對(duì)于任意給定的頂點(diǎn)，輸出一條符合上述要求的路徑
解題思路：
這是一道經(jīng)典的遍歷問(wèn)題（DFS），由于題目要求遍歷全部，那么肯定要做標(biāo)記，因此立馬想到DFS深度優(yōu)先算法。具體思路如下：
①了解國(guó)際象棋以及國(guó)際象棋騎士的走法
國(guó)際象棋和中國(guó)象棋，大同小異，畢竟中國(guó)象棋是老祖先。國(guó)際象棋棋子放在格子中，中國(guó)象棋放在點(diǎn)上，且國(guó)際象棋有64個(gè)格子。國(guó)際象棋的騎士和中國(guó)象棋的馬功能相當(dāng)，都可以走八個(gè)方位。走法是走“日”字，或英文字母大寫(xiě)的“L”形：即先向左（或右）走1格，再向上（或下）走2格；或先向左（或右）走2格，再向上（或下）走1格。與中國(guó)象棋的馬不同，國(guó)際象棋的馬可以跳過(guò)路上的其他棋子，不受拐腳的限制。
解題需要我們可以把格子抽象成一個(gè)點(diǎn)，那么國(guó)際象棋的騎士走法就是一個(gè)日字。
②設(shè)置標(biāo)記
初始化數(shù)組，讓每個(gè)元素初始化為0，并且初始化一個(gè)記錄騎士遍歷次數(shù)的cal也為0
int cal = 0; //統(tǒng)計(jì)走的順序
//初始化為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
};③判斷是否超界和是否被訪問(wèn)
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) //判斷是否被訪問(wèn)
{
?? ?if (chress[x][y] != 0)
?? ??? ?return true;
?? ?else
?? ??? ?return false;
}④遞歸主體
void dfs(int x,int y)
{?? ?
?? ?if (cal == 64) //如果遍歷完則退出棋盤(pán)一共64個(gè)位置
?? ??? ?return;
?? ?if (!ifVisited(x, y) && !ifOut(x, y)) //如果沒(méi)有被訪問(wèn)且沒(méi)有出界 則訪問(wèn)
?? ?{
?? ??? ?cal++; ??
?? ??? ?chress[x][y] = cal; //做標(biāo)記
?? ??? ?dfs(x + 2, y + 1);?? ?//騎士走法有八個(gè)方位，故八個(gè) 方位都遍歷
?? ??? ?dfs(x - 2, y - 1); ? //八個(gè)遞歸的順序可以改，順序不一樣，結(jié)果不一樣
?? ??? ?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其中包括已經(jīng)被訪問(wèn)了，和沒(méi)有被訪問(wèn)且在界外的
?? ??? ?return;
}⑤總代碼如下（編譯器vs2013）
#include"stdafx.h"
#include<iostream>
#include<iomanip>
using namespace std;
int cal = 0; //統(tǒng)計(jì)走的順序
//棋盤(pán)初始化為0做標(biāo)記
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) //判斷是否已經(jīng)被訪問(wèn)
{
?? ?if (chress[x][y] != 0)
?? ??? ?return true;
?? ?else
?? ??? ?return false;
}
void dfs(int x,int y)
{?? ?
?? ?if (cal == 64) //如果遍歷完則退出棋盤(pán)一共64個(gè)位置
?? ??? ?return;
?? ?if (!ifVisited(x, y) && !ifOut(x, y)) //如果沒(méi)有被訪問(wèn)且沒(méi)有出界 則訪問(wèn)
?? ?{
?? ??? ?cal++; ??
?? ??? ?chress[x][y] = cal; //做標(biāo)記
?? ??? ?dfs(x + 2, y + 1);?? ?//騎士走法有八個(gè)方位，故八個(gè) 方位都遍歷
?? ??? ?dfs(x - 2, y - 1); ?//八個(gè)遞歸的順序可以改，順序不一樣，結(jié)果不一樣?
?? ??? ?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 << "請(qǐng)輸入騎士初始的位置：";
?? ?while (1)
?? ?{
?? ??? ?cin >> x >> y; ? ?//輸入坐標(biāo)
?? ??? ?if (x > 7 || x<0 || y> 7 || y < 0)
?? ??? ??? ?cout << "初始位置輸入錯(cuò)誤請(qǐng)重新輸入" << endl;
?? ??? ?else
?? ??? ??? ?break;
?? ?}
?? ?dfs(x,y);
?? ?for (int i = 0; i < 8; i++) ?//輸出打印測(cè)試
?? ?{
?? ??? ?for (int j = 0; j < 8; j++)
?? ??? ??? ?cout << setw(2)<<chress[i][j]<<" ?";
?? ??? ?cout << endl;
?? ?}
?? ?return 0;
}⑥測(cè)試截圖：
以上就是本文的全部?jī)?nèi)容，希望對(duì)大家的學(xué)習(xí)有所幫助，也希望大家多多支持腳本之家。
相關(guān)文章
C語(yǔ)言庫(kù)函數(shù)qsort的使用及模擬實(shí)現(xiàn)
這篇文章主要介紹了C語(yǔ)言庫(kù)函數(shù)qsort的使用及模擬實(shí)現(xiàn)，文章圍繞主題展開(kāi)詳細(xì)的內(nèi)容介紹，具有一定的參考價(jià)值，需要的小伙伴可以參考一下2022-08-08
c++如何在主函數(shù)文件中調(diào)用其他函數(shù)文件
這篇文章主要介紹了c++如何在主函數(shù)文件中調(diào)用其他函數(shù)文件問(wèn)題,具有很好的參考價(jià)值,希望對(duì)大家有所幫助,如有錯(cuò)誤或未考慮完全的地方,望不吝賜教2023-08-08
C++根據(jù)傳入的函數(shù)指針來(lái)解析需要的參數(shù)(推薦)
C++可以根據(jù)傳入的函數(shù)指針，獲取自己需要的參數(shù)類(lèi)型，然后根據(jù)參數(shù)源中獲取需要的參數(shù)，具體實(shí)現(xiàn)方式大家參考下本文2018-05-05
C語(yǔ)言實(shí)現(xiàn)快速排序改進(jìn)版
這篇文章主要為大家詳細(xì)介紹了C語(yǔ)言實(shí)現(xiàn)快速排序的改進(jìn)代碼，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2018-08-08
這篇文章主要給大家介紹了關(guān)于C++序列操作函數(shù)學(xué)習(xí)的相關(guān)資料,文中通過(guò)實(shí)例代碼介紹的非常詳細(xì),對(duì)大家學(xué)習(xí)或者使用C++具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友可以參考下
2022-02-02 
這篇文章主要為大家詳細(xì)介紹了C++實(shí)現(xiàn)單鏈表的構(gòu)造，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下
2020-04-04 
Qt是一個(gè)著名的GUI框架,用來(lái)開(kāi)發(fā)和用戶(hù)交互的圖形界面,作為GUI框架,豐富的控件和靈活的事件機(jī)制是不可或缺的,Qt在這一方面做得非常優(yōu)秀,下面這篇文章主要給大家介紹了關(guān)于Qt輸入類(lèi)控件用法的相關(guān)資料,需要的朋友可以參考下
2024-08-08 
C++標(biāo)準(zhǔn)庫(kù)實(shí)現(xiàn)WAV文件讀寫(xiě)的操作
本文將使用標(biāo)準(zhǔn)C++庫(kù)實(shí)現(xiàn)對(duì)數(shù)據(jù)為PCM格式的WAV文件的讀寫(xiě)操作，只使用標(biāo)準(zhǔn)C++庫(kù)函數(shù)，不依賴(lài)于其他的庫(kù)，對(duì)C++標(biāo)準(zhǔn)庫(kù)實(shí)現(xiàn)WAV文件讀寫(xiě)相關(guān)知識(shí)感興趣的朋友一起看看吧
2022-01-01 
C++任意線程通過(guò)hwnd實(shí)現(xiàn)將操作發(fā)送到UI線程執(zhí)行
做Windows界面開(kāi)發(fā)時(shí),經(jīng)常需要在多線程環(huán)境中將操作拋到主線程執(zhí)行,下面我們就來(lái)學(xué)習(xí)一下如何在不需要重新定義消息以及接收消息的情況下實(shí)現(xiàn)這一要求,感興趣的可以了解下
2024-03-03