C++騎士游歷問題的示例分析

這篇文章主要介紹了C++騎士游歷問題的示例分析，具有一定借鑒價值，感興趣的朋友可以參考下，希望大家閱讀完這篇文章之后大有收獲，下面讓小編帶著大家一起了解一下。

騎士游歷問題：在國際棋盤上使一個騎士遍歷所有的格子一遍且僅一遍，對于任意給定的頂點(diǎn)，輸出一條符合上述要求的路徑

解題思路：

這是一道經(jīng)典的遍歷問題（DFS），由于題目要求遍歷全部，那么肯定要做標(biāo)記，因此立馬想到DFS深度優(yōu)先算法。具體思路如下：

①了解國際象棋以及國際象棋騎士的走法

國際象棋和中國象棋，大同小異，畢竟中國象棋是老祖先。國際象棋棋子放在格子中，中國象棋放在點(diǎn)上，且國際象棋有64個格子。國際象棋的騎士和中國象棋的馬功能相當(dāng)，都可以走八個方位。走法是走“日”字，或英文字母大寫的“L”形：即先向左（或右）走1格，再向上（或下）走2格；或先向左（或右）走2格，再向上（或下）走1格。與中國象棋的馬不同，國際象棋的馬可以跳過路上的其他棋子，不受拐腳的限制。
解題需要我們可以把格子抽象成一個點(diǎn)，那么國際象棋的騎士走法就是一個日字。

②設(shè)置標(biāo)記

初始化數(shù)組，讓每個元素初始化為0，并且初始化一個記錄騎士遍歷次數(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
};

③判斷是否超界和是否被訪問

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; //做標(biāo)記
        dfs(x + 2, y + 1);    //騎士走法有八個方位，故八個 方位都遍歷
        dfs(x - 2, y - 1);   //八個遞歸的順序可以改，順序不一樣，結(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)被訪問了，和沒有被訪問且在界外的
        return;
}

⑤總代碼如下（編譯器vs2013）

#include"stdafx.h"
#include<iostream>
#include<iomanip>
using namespace std;
int cal = 0; //統(tǒng)計(jì)走的順序
//棋盤初始化為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)被訪問
{
    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; //做標(biāo)記
        dfs(x + 2, y + 1);    //騎士走法有八個方位，故八個 方位都遍歷
        dfs(x - 2, y - 1);  //八個遞歸的順序可以改，順序不一樣，結(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 << "請輸入騎士初始的位置：";
    while (1)
    {
        cin >> x >> y;    //輸入坐標(biāo)
        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;
}

⑥測試截圖：

感謝你能夠認(rèn)真閱讀完這篇文章，希望小編分享的“C++騎士游歷問題的示例分析”這篇文章對大家有幫助，同時也希望大家多多支持億速云，關(guān)注億速云行業(yè)資訊頻道，更多相關(guān)知識等著你來學(xué)習(xí)!