本次我們探討一下迷宮小游戲。
成都創(chuàng)新互聯(lián)是一家專業(yè)提供五通橋企業(yè)網(wǎng)站建設(shè),專注與做網(wǎng)站、成都做網(wǎng)站、H5技術(shù)、小程序制作等業(yè)務(wù)。10年已為五通橋眾多企業(yè)、政府機(jī)構(gòu)等服務(wù)。創(chuàng)新互聯(lián)專業(yè)網(wǎng)站設(shè)計(jì)公司優(yōu)惠進(jìn)行中。讓我們來(lái)探討一下怎樣可以得到一條通路，采用棧來(lái)實(shí)現(xiàn)。
當(dāng)是通路的時(shí)候，節(jié)點(diǎn)壓棧。當(dāng)走到盡頭不通時(shí)，出棧，尋找交叉口，尋找通路。
像這樣在第一行存放迷宮的規(guī)格（在這里為傳參少，定義正方形迷宮），設(shè)計(jì)迷宮，將迷宮以.txt格式存放在目錄下（可以是任何地方，下文以默認(rèn)路徑為例）。
假設(shè)入口為(2,0)，出口為迷宮最后一行任意位置。
MAZE.h
#pragma once #define _CRT_SECURE_NO_WARNINGS 1 #includeusing namespace std; #include #include class Pos //迷宮每一點(diǎn)的坐標(biāo) { public: Pos(int row,int col) :_row(row) , _col(col) {} int _row; int _col; }; void PrintPos(Pos& pos)// 打印節(jié)點(diǎn)坐標(biāo) { cout << "(" << pos._row << ", " << pos._col << ") "; } int* GetMaze(int& N)//從文件中打開迷宮 { FILE *font = fopen("maze.txt", "r"); assert(font != NULL);//打不開迷宮文件無(wú)意義 char ch; while ((ch = fgetc(font)) != '\n') { N = N * 10 + ch - '0'; } int *a = new int[N*N]; for (int i = 0; i < N*N, (ch = fgetc(font)) != EOF;) { if (ch == '1' || ch == '0') { a[i] = ch - '0'; i++; } } return a; } void PrintMaze(int *a, const int N)//打印迷宮 { cout << "\n迷宮地圖 ('0'為路, '1'為墻)" << endl; for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { cout << a[i * 10 + j] << " "; } cout << endl; } } bool IsOverScope(Pos pos, const int N)//判斷是否越界 { if (pos._col < 0 || pos._col >= N || pos._row < 0 || pos._row >= N) { return true; } return false; } bool IsEndPoint(Pos pos, const int N) //判斷是否為終點(diǎn)：設(shè)迷宮終點(diǎn)為能到達(dá)迷宮N-1行 { if (pos._col >= 0 && pos._col < N && pos._row == N - 1) { return true; } return false; } bool SearchMazePath(int* a, const int N, Pos enrty, stack & paths) //尋找通路 { //若某一位置節(jié)點(diǎn)為0，進(jìn)行壓棧，且將數(shù)據(jù)改為2，尋找此節(jié)點(diǎn)上下左右位置為0的節(jié)點(diǎn)，再進(jìn)行壓棧， //若某一位置上下左右沒(méi)有為0的節(jié)點(diǎn)，就出棧尋找上一個(gè)節(jié)點(diǎn)上下左右為0的節(jié)點(diǎn)進(jìn)行壓棧 assert(a); Pos top = paths.top(); a[top._row*N + top._col] = 2; while (!IsOverScope(paths.top(), N))//每次都要判斷坐標(biāo)是否越界、還要考慮出口旁邊也是出口的情況就會(huì)多走幾次 { //判斷是否到達(dá)出口 if (IsEndPoint(top, N)) { return true; } if (0 == a[(top._row - 1)*N + top._col])//上 { a[(top._row - 1)*N + top._col] = 2; Pos tmp(top._row - 1, top._col); paths.push(tmp); top = paths.top(); continue; } if (0 == a[top._row * N + top._col + 1])//右 { a[top._row * N + top._col + 1] = 2; Pos tmp(top._row, top._col + 1); paths.push(tmp); top = paths.top(); continue; } if (0 == a[(top._row + 1)*N + top._col])//下 { a[(top._row + 1)*N + top._col] = 2; Pos tmp(top._row + 1, top._col); paths.push(tmp); top = paths.top(); continue; } if (0 == a[top._row * N + top._col - 1])//左 { a[top._row * N + top._col - 1] = 2; Pos tmp(top._row, top._col - 1); paths.push(tmp); top = paths.top(); continue; } //if (0 == a[top._row * N + top._col + 1] && top._col + 1 < N)//右 //{ // a[top._row * N + top._col + 1] = 2; // Pos tmp(top._row, top._col + 1); // paths.push(tmp); // top = paths.top(); // continue; //} //回退 if (a[top._row*N + top._col] == 2 && !paths.empty()) { paths.pop(); if (!paths.empty()) { top = paths.top(); continue; } else { return false; } } } //if (IsOverScope(top, N) || paths.empty())//從上左右出來(lái) return false; } void PrintPath(stack paths) //打印通路 { //最少Paths中有一個(gè)元素enrty在最底層 assert(!paths.empty()); cout << "通路： " << endl;; while (!paths.empty()) { PrintPos(paths.top()); paths.pop(); } cout << endl; }
test.cpp
重慶分公司
重慶分公司
#include"MAZE.h"
void test()
{
//假設(shè)迷宮為N*N型正方形
int N = 0;
int *a = GetMaze(N);
PrintMaze(a, N);
Pos enrty(2,0);
stack paths;
paths.push(enrty);
if (SearchMazePath((int*)a, N, enrty, paths))
{
PrintMaze(a, N);
PrintPath(paths);
}
else
{
PrintMaze(a, N);
cout << "There is not a path in this maze!" << endl;
}
}
int main()
{
test();
system("pause");
return 0;
} 讓我們來(lái)看看運(yùn)行結(jié)果。
再試試將最后一行的‘0’改為1，讓它變成無(wú)通路的迷宮
我們可以在思考一下：
當(dāng)有好幾條通路的時(shí)候，我們可以得到最短路嗎？
我們可以得到以下思路：
記錄最小路的步數(shù) ,到達(dá)出口時(shí)將出口變?yōu)? ,尋找下一條出口,然后更新最短路.
若要尋找這條最短路，那就可以在尋找一次，當(dāng)通路的步數(shù)與最短路步數(shù)一致時(shí)輸出通路。
但是上述方法存在很大的問(wèn)題：雖然可以得到一個(gè)結(jié)果，但是不能夠保證就是最短的。
因?yàn)椋?dāng)按照上述編程尋找通路的邏輯 “上右下左” 順序?qū)ふ彝窌r(shí)，就可能會(huì)把另一條更短的通路堵住，從而影響最短路的結(jié)果。
那到底怎么做呢？ 期待下一篇博客。
另外有需要云服務(wù)器可以了解下創(chuàng)新互聯(lián)scvps.cn，海內(nèi)外云服務(wù)器15元起步，三天無(wú)理由+7*72小時(shí)售后在線，公司持有idc許可證，提供“云服務(wù)器、裸金屬服務(wù)器、高防服務(wù)器、香港服務(wù)器、美國(guó)服務(wù)器、虛擬主機(jī)、免備案服務(wù)器”等云主機(jī)租用服務(wù)以及企業(yè)上云的綜合解決方案，具有“安全穩(wěn)定、簡(jiǎn)單易用、服務(wù)可用性高、性價(jià)比高”等特點(diǎn)與優(yōu)勢(shì)，專為企業(yè)上云打造定制，能夠滿足用戶豐富、多元化的應(yīng)用場(chǎng)景需求。
