C++ DFS算法實現(xiàn)走迷宮自動尋路
更新時間：2021年05月17日 15:34:18 作者：白家名
這篇文章主要為大家詳細介紹了C++ DFS算法實現(xiàn)走迷宮自動尋路，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下
C++ DFS算法實現(xiàn)走迷宮自動尋路，供大家參考，具體內(nèi)容如下
深度優(yōu)先搜索百度百科解釋：
事實上，深度優(yōu)先搜索屬于圖算法的一種，英文縮寫為DFS即Depth First Search.其過程簡要來說是對每一個可能的分支路徑深入到不能再深入為止，而且每個節(jié)點只能訪問一次.
運行效果：
說明：
深度優(yōu)先搜索算法是在我在圖的部分接觸到的，后來才發(fā)現(xiàn)它也可以不用在圖的遍歷上，它是一個獨立的算法，它也可以直接用在一個二維數(shù)組上。
其算法原理和實現(xiàn)步驟在代碼中已經(jīng)有了很好的體現(xiàn)了，這里就不再贅述。
在程序中實現(xiàn)了手動操控走迷宮和自動走迷宮兩種模式，并且可在自動走完迷宮后顯示行走的路徑。
如果要修改程序使用的迷宮地圖只需要修改map二維地圖數(shù)組和兩個地圖寬高的常量值即可。同樣可以使用自動走迷宮的模式。
理論上這種算法可以對任意大小任意復(fù)雜的迷宮搜索路徑，但是因為這種算法是用遞歸實現(xiàn)的，占用空間較大，地圖大小增大也會多使用很多的空間，受限于堆?？臻g的限制我在把地圖大小增加到2020的時候運行自動尋路模式就會報堆棧溢出異常了。我在代碼準(zhǔn)備了1818和15*15的兩個迷宮地圖二維數(shù)組用于測試。
編譯環(huán)境：
Windows VS2019
代碼：
Game.h 游戲類
#pragma once
#include <iostream>
#include <map>
#include <conio.h>
#include <vector>
#include <windows.h>
using namespace std;
//地圖寬高常量
constexpr unsigned int mapWidth = 18;
constexpr unsigned int mapHeight = 18;
//游戲類
class Game
{
private:
map<int, string> cCMAEMap; //地圖數(shù)組元素對應(yīng)字符
map<char, int*> movDistanceMap; //按鍵對應(yīng)移動距離
int px, py; //玩家坐標(biāo)
int dArr[4][2] = { {0, -1}, {0, 1}, {-1, 0}, {1, 0} }; //數(shù)值和移動方向?qū)?yīng)數(shù)組
vector<int*> tempPathVec; //路徑向量
vector<vector<int*>> allPathVec;//存儲所有路徑向量
//檢查參數(shù)位置是否可走
bool check(int x, int y, int(*map)[mapWidth])
{
//判斷修改后的玩家坐標(biāo)是否越界、修改后的玩家坐標(biāo)位置是否可走
if (x < 0 || x >= mapWidth || y < 0 || y >= mapHeight || (map[y][x] != 0 && map[y][x] != 3))
return false;
return true;
}
//控制玩家移動函數(shù)
bool controlMove (int(*map)[mapWidth])
{
//鍵盤按下時
if (!_kbhit()) return false;
char key = _getch();
if (key != 'w' && key != 's' && key != 'a' && key != 'd')
return false;
int temp_x = px, temp_y = py; //臨時記錄沒有改變之前的玩家坐標(biāo)
px += movDistanceMap[key][0];
py += movDistanceMap[key][1];
//如果位置不可走則撤銷移動并結(jié)束函數(shù)
if (!check(px, py, map))
{
px = temp_x, py = temp_y;
return false;
}
//判斷是否已到達終點
if (map[py][px] == 3)
{
//打印信息并返回true
cout << "勝利！" << endl;
return true;
}
map[temp_y][temp_x] = 0; //玩家原本的位置重設(shè)為0路面
map[py][px] = 2; //玩家移動后的位置設(shè)為玩家2
//清屏并打印修改后地圖
system("cls");
printMap(map);
return false;
}
//用對應(yīng)圖形打印地圖
void printMap(int(*map)[mapWidth])
{
for (int i = 0; i < mapHeight; i++)
{
for (int j = 0; j < mapWidth; j++)
cout << cCMAEMap[map[i][j]];
cout << endl;
}
}
//初始化map容器
void initMapContainer()
{
//數(shù)組元素和字符對應(yīng)
string cArr[4] = { " ", "■", "♀", "★" };
for (int i = 0; i < 4; i++)
cCMAEMap.insert(pair <int, string>(i, cArr[i]));
//輸入字符和移動距離對應(yīng)
char kArr[4] = { 'w', 's', 'a', 'd' };
for (int i = 0; i < 4; i++)
movDistanceMap.insert(pair <char, int*>(kArr[i], dArr[i]));
}
//找到玩家所在地圖的位置
void findPlayerPos(const int(*map)[mapWidth])
{
for (int i = 0; i < mapHeight; i++)
for (int j = 0; j < mapWidth; j++)
if (map[i][j] == 2)
{
px = j, py = i;
return;
}
}
//深度優(yōu)先搜索
void dfs(int cx, int cy, int(*map)[mapWidth])
{
//把當(dāng)前玩家位置插入到數(shù)組
tempPathVec.push_back(new int[2] {cx, cy});
//循環(huán)四個方向上下左右
for (int i = 0; i < 4; i++)
{
int x = cx + dArr[i][0]; //玩家下一個位置的坐標(biāo)
int y = cy + dArr[i][1];
//檢查下一個位置是否可走
if (!check(x, y, map))
continue;
if (map[y][x] == 3) //已到達終點
{
tempPathVec.push_back(new int[2]{ x, y }); //把終點位置插入到向量中
allPathVec.push_back(tempPathVec);
return;
}
//為普通路徑
else
{
map[cy][cx] = -1; //當(dāng)前位置臨時設(shè)為-1，遞歸搜索時不可走原路，非0且非3的位置都不可走
dfs(x, y, map); //用下一個位置作為參數(shù)遞歸
map[cy][cx] = 0; //遞歸完成后將當(dāng)前位置重設(shè)為0，可走路徑
}
}
//最后沒有找到可走的路徑則刪除向量最后一個元素，此時函數(shù)結(jié)束遞歸退回到上一層
tempPathVec.pop_back();
}
//輸出路徑信息
void printPathInformation()
{
//int minSizePathIndex = 0; //記錄最短路徑在路徑向量中的下標(biāo)
//for (int i = 0; i < allPathVec.size(); i++)
//{
// cout << allPathVec.at(i).size() << " ";
// if (allPathVec.at(i).size() < allPathVec.at(minSizePathIndex).size())
// minSizePathIndex = i;
//}
//cout << endl << "最小長度：" << allPathVec.at(minSizePathIndex).size() << endl;
輸出最短路徑信息
//for (auto dArr2 : allPathVec.at(minSizePathIndex))
// cout << dArr2[0] << "_" << dArr2[1] << " ";
//輸出所有路徑信息
//for (auto arr : allPathVec)
//{
// for (auto dArr2 : arr)
// cout << dArr2[0] << "__" << dArr2[1] << " ";
// cout << endl;
//}
}
//尋找路徑
int findPath(int(*map)[mapWidth])
{
findPlayerPos(map); //找到玩家所在地圖中的位置
//如果多次調(diào)用findPaths函數(shù)，則需要先清除上一次調(diào)用時在向量中遺留下來的數(shù)據(jù)
tempPathVec.clear();
allPathVec.clear();
dfs(px, py, map); //找到所有路徑插入到allPathVec
//找到最短路徑在allPathVec中的下標(biāo)
int minSizePathIndex = 0; //記錄最短路徑在路徑向量中的下標(biāo)
for (int i = 0; i < allPathVec.size(); i++)
{
if (allPathVec.at(i).size() < allPathVec.at(minSizePathIndex).size())
minSizePathIndex = i;
}
return minSizePathIndex;
}
//顯示路徑
void showPath(int(*map)[mapWidth], vector<int*> tempPathVec)
{
//將能找到的最短的路徑上的元素賦值全部賦值為2并輸出
for (auto tempDArr : tempPathVec)
map[tempDArr[1]][tempDArr[0]] = 2;
system("cls");
printMap(map); //打印地圖
}
//手動模式
void manualMode(int(*map)[mapWidth])
{
while (!controlMove(map)) //游戲循環(huán)
Sleep(10);
}
//自動模式
void automaticMode(int(*map)[mapWidth])
{
//找到最短路徑
vector<int*> tempPathVec = allPathVec.at(findPath(map));
for (int i = 1; i < tempPathVec.size(); i++)
{
map[tempPathVec[i - 1][1]][tempPathVec[i - 1][0]] = 0;
map[tempPathVec[i][1]][tempPathVec[i][0]] = 2;
system("cls");
printMap(map); //打印地圖
Sleep(200);
}
cout << "勝利！是否打印完整路徑？（Y / N）" << endl;
char key = _getch();
if(key == 'Y' || key == 'y')
showPath(map, tempPathVec);
}
public:
//構(gòu)造
Game(int(*map)[mapWidth], char mode)
{
initMapContainer(); //初始化map容器
findPlayerPos(map); //找到玩家所在地圖中的位置
system("cls");
printMap(map); //先打印一遍地圖 ♀ ■ ★
(mode == '1') ? manualMode(map) : automaticMode(map);
}
//析構(gòu)釋放內(nèi)存
~Game()
{
for (auto it = tempPathVec.begin(); it != tempPathVec.end(); it++)
{
delete* it;
*it = nullptr;
}
tempPathVec.clear();
//這里不會釋放allPathVec了
allPathVec.clear();
}
};
迷宮.cpp main函數(shù)文件
#include "Game.h"
//光標(biāo)隱藏
void HideCursor()
{
CONSOLE_CURSOR_INFO cursor_info = { 1, 0 };
SetConsoleCursorInfo(GetStdHandle(STD_OUTPUT_HANDLE), &cursor_info);
}
int main()
{
HideCursor(); //光標(biāo)隱藏
//0空地，1墻，2人， 3出口
//int map[mapHeight][mapWidth] = {
// 2, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 1, 1,
// 0, 0, 1, 1, 0, 1, 1, 0, 0, 0, 1, 0, 0, 0, 1,
// 1, 0, 1, 0, 0, 0, 1, 0, 1, 1, 1, 0, 1, 0, 0,
// 1, 0, 1, 0, 1, 0, 1, 0, 0, 0, 0, 0, 1, 1, 1,
// 1, 1, 1, 0, 1, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0,
// 0, 0, 0, 0, 1, 1, 1, 1, 0, 1, 0, 1, 1, 1, 0,
// 0, 1, 0, 0, 0, 0, 1, 0, 0, 1, 0, 1, 0, 1, 0,
// 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 0, 0, 0, 1, 1,
// 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0,
// 1, 0, 1, 1, 1, 1, 0, 0, 1, 1, 1, 0, 0, 1, 0,
// 1, 0, 1, 0, 0, 1, 0, 1, 1, 0, 0, 0, 1, 1, 1,
// 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 1, 1, 0, 1,
// 0, 1, 1, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0,
// 0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 0, 1, 1, 1, 0,
// 1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 1, 0, 3,
//};
int map[mapHeight][mapWidth]
{
2, 0, 1, 0, 0, 0, 1, 1, 0, 0, 0, 1, 1, 0, 0, 1, 1, 1,
0, 0, 0, 0, 1, 0, 0, 0, 1, 1, 0, 1, 0, 1, 1, 0, 0, 1,
1, 1, 0, 1, 0, 0, 1, 0, 0, 1, 0, 1, 0, 1, 0, 0, 1, 0,
1, 0, 0, 0, 0, 1, 1, 0, 1, 0, 0, 0, 0, 1, 0, 0, 1, 0,
1, 1, 0, 1, 1, 1, 0, 1, 1, 0, 1, 1, 0, 0, 0, 1, 1, 1,
0, 1, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 1, 1, 1, 1,
0, 0, 0, 0, 0, 1, 1, 0, 1, 0, 1, 1, 0, 0, 0, 1, 0, 1,
0, 1, 1, 0, 1, 1, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 0, 0,
0, 0, 0, 1, 0, 1, 0, 1, 0, 0, 0, 1, 0, 1, 1, 0, 1, 1,
1, 1, 1, 0, 0, 1, 0, 1, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0,
1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 1, 1, 0, 0, 1, 0,
0, 1, 1, 0, 1, 0, 1, 1, 1, 0, 1, 0, 1, 0, 1, 0, 1, 1,
1, 0, 0, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 0, 1,
1, 0, 0, 1, 1, 1, 1, 0, 0, 1, 0, 0, 1, 1, 0, 1, 0, 0,
0, 0, 1, 0, 1, 0, 0, 0, 1, 1, 0, 1, 0, 0, 1, 0, 0, 1,
0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 1, 0, 1, 0, 1,
1, 0, 0, 0, 0, 1, 0, 0, 1, 0, 1, 1, 1, 1, 0, 1, 0, 0,
1, 1, 1, 1, 0, 1, 1, 0, 0, 0, 0, 0, 1, 0, 1, 1, 0, 3,
};
//復(fù)制一個一樣的數(shù)組以保證重新開始游戲時可以重置數(shù)組
int mapCopy[mapHeight][mapWidth];
memcpy(mapCopy, map, sizeof(mapCopy));
while (true)
{
cout << "選擇模式：1，手動 2，自動" << endl;
char key = _getch();
Game game(mapCopy, key); //進入游戲
cout << "輸入r重新開始：" << endl;
key = _getch();
if (key != 'r' && key != 'R') //輸入值不為r則結(jié)束程序
break;
memcpy(mapCopy, map, sizeof(mapCopy)); //重新賦值
system("cls");
}
return 0;
}
以上就是本文的全部內(nèi)容，希望對大家的學(xué)習(xí)有所幫助，也希望大家多多支持腳本之家。
相關(guān)文章
在開發(fā)中經(jīng)常會遇到有符號和無符號之間的轉(zhuǎn)換問題，如果不清楚問題根源，很難解決bug，今天小編通過本文給大家分享c++有符號無符號轉(zhuǎn)換問題，需要的朋友參考下2021-07-07
Qt使用QListWidget實現(xiàn)自定義Item
這篇文章主要為大家詳細介紹了Qt如何使用QListWidget實現(xiàn)自定義Item的效果,文中的示例代碼講解詳細,感興趣的小伙伴可以跟隨小編一起學(xué)習(xí)一下2023-10-10
C語言安全編碼之?dāng)?shù)值中的sizeof操作符
這篇文章主要介紹了C語言安全編碼的數(shù)值中的sizeof操作符用法注意事項,需要的朋友可以參考下2014-07-07
QT quick-Popup彈出窗口自定義的實現(xiàn)
本文主要介紹了QT quick-Popup彈出窗口自定義的實現(xiàn)，文中通過示例代碼介紹的非常詳細，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2021-07-07
C++讀入"N,X,Y,Z"格式文本文件到Eigen3 Matrix
這篇文章主要介紹了C++讀入"N,X,Y,Z"格式文本文件到Eigen3 Matrix，本文通過實例代碼給大家介紹的非常詳細，對大家的學(xué)習(xí)或工作具有一定的參考借鑒價值,需要的朋友可以參考下2020-04-04
這篇文章主要介紹了C語言中形參和實參詳解及實例代碼的相關(guān)資料,需要的朋友可以參考下2017-05-05
C語言SetConsoleCursorInfo函數(shù)使用方法
這篇文章介紹了C語言SetConsoleCursorInfo函數(shù)的使用方法，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2021-12-12
這篇文章主要介紹了C++實現(xiàn)LeetCode(20.驗證括號),本篇文章通過簡要的案例,講解了該項技術(shù)的了解與使用,以下就是詳細內(nèi)容,需要的朋友可以參考下2021-07-07
這篇文章主要介紹了vs2019安裝及簡單處理方法，本文是一篇非常詳細的教程，通過圖文并茂的形式給大家介紹的非常詳細，對大家的學(xué)習(xí)或工作具有一定的參考借鑒價值，需要的朋友可以參考下2020-06-06
數(shù)據(jù)結(jié)構(gòu)之Treap詳解
這篇文章主要介紹了數(shù)據(jù)結(jié)構(gòu)之Treap詳解,本文講解了Treap的基本知識、Treap的基本操作、Treap的高級操作技巧等,需要的朋友可以參考下2014-08-08