您好,登錄后才能下訂單哦!
在我們學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)的時(shí)候都曾經(jīng)見過迷宮游戲,迷宮游戲的實(shí)現(xiàn)其實(shí)并不難,但是,我們在實(shí)現(xiàn)每一個算法的時(shí)候都應(yīng)該想一想這個問題的每一個解。最近,博主已經(jīng)開始重溫?cái)?shù)據(jù)結(jié)構(gòu)啦,記得我們以前學(xué)習(xí)這里的時(shí)候,老師會用隊(duì)列來實(shí)現(xiàn)迷宮最優(yōu)解的尋找,氮素呢,博主就是這么可愛,博主就是想試試用棧來找一下。
在實(shí)現(xiàn)之前讓我們先來復(fù)習(xí)一下棧的特點(diǎn):first in last out
對于棧這種數(shù)據(jù)結(jié)構(gòu)我們只能在棧頂對其操作,根據(jù)實(shí)際情況可將其實(shí)現(xiàn)成鏈?zhǔn)交蛘唔樞蚪Y(jié)構(gòu)。但是一般情況下我們都會實(shí)現(xiàn)成順序結(jié)構(gòu),因?yàn)闂5奶攸c(diǎn)導(dǎo)致了順序結(jié)構(gòu)管理方便,并且CPU緩存利用率更高。下面我們來簡單的講解一下迷宮小游戲
為了避免用戶操作的不便性,我們選擇將迷宮提前寫好放在一個叫做"Maze.h"的文件中
#define _CRT_SECURE_NO_WARNINGS 1 #pragma once #include<cassert> #include<iostream> #include<fstream> #include<stack> using namespace std; struct Pos { size_t _x; size_t _y; Pos(size_t x, size_t y) :_x(x), _y(y) {} }; stack<Pos> min; bool IsValid(int *a, Pos cur, size_t R, size_t C) { if ((a[cur._x*C + cur._y] == 0) && (cur._x < R) && (cur._y < C)) return true; else return false; } void PrintMap(int *Map, size_t m, size_t n) { for (size_t i = 0; i < m; i++) { for (size_t j = 0; j < n; j++) { std::cout << Map[i*n + j] << " "; } std::cout << std::endl; } } void GetMaze(int *a,size_t Row,size_t Col,std::ifstream& fout) { size_t ch = 0; for (size_t i = 0; i < Row; i++) { for (size_t j = 0; j < Col;) { ch = fout.get()-'0'; if (ch == 0 || ch == 1) { a[i*Col + j] = ch; j++; } else continue; } } PrintMap(a, Row, Col); } bool Check(int *a,Pos entry,int R,int C) { Pos Up = entry; Pos Down = entry; Pos Left = entry; Pos Right = entry; Down._x++; Right._y++; Up._x--; Left._y--; if (IsValid(a, Down, R, C) || IsValid(a, Up, R, C) || IsValid(a, Left, R, C) || IsValid(a, Right, R, C)) return true; else return false; } bool GamePlay(int *a, Pos entry, size_t R, size_t C) { assert(a); stack<Pos> s1; Pos man = entry; Pos next = man; Pos cur = entry; while ( 1 ) { if (!Check(a, man, R, C)) { cout << "最佳路徑長度:"; cout << min.size() << endl; return true; } s1.push(man); while (!s1.empty()) { a[man._x*C + man._y] = 2; if (man._x == (R - 1) || man._y == (C - 1)) { cout << "Find&end" << endl; if ((s1.size() < min.size()) || min.size() == 0) min = s1; while (!s1.empty()) { cur = s1.top(); s1.pop(); if (Check(a, cur, R, C)) { man = cur; break; } } if (s1.empty()) { cout << "最佳路徑長度:"; cout << min.size() << endl; return true; } } //********************************************下 next = man; next._x++; if (IsValid(a, next, R, C)) { s1.push(man); man = next; continue; } //********************************************右 next = man; next._y++; if (IsValid(a, next, R, C)) { s1.push(man); man = next; continue; } //********************************************左 next = man; next._y--; if (IsValid(a, next, R, C)) { s1.push(man); man = next; continue; } //********************************************上 next._x--; if (IsValid(a, next, R, C)) { s1.push(man); man = next; continue; } else { man = s1.top(); s1.pop(); } } man = entry; } } void GameTest() { //**********************從文件讀入迷宮大小********************** ifstream fout("Maze.txt"); stack<int> s1; int Row = 0; int Col = 0; char ch = fout.get(); while (ch != ' ') { int tmp = ch - '0'; s1.push(tmp); ch = fout.get(); } int c = 0; while (!s1.empty()) { Row += s1.top()*(int)pow(10, c); s1.pop(); c++; } ch = fout.get(); while (ch != ' '&&ch != '\n') { int tmp = ch - '0'; s1.push(tmp); ch = fout.get(); } c = 0; while (!s1.empty()) { Col += (int)s1.top()*(int)pow(10, c); s1.pop(); c++; } int *a = new int[Row*Col]; //******************************************************** Pos entry(0, 1); cout << endl << "*********** Map **********" << endl; GetMaze(a, Row, Col, fout); GamePlay(a, entry, Row, Col); cout << endl << "*********** Map **********" << endl; PrintMap(a, Row, Col); fout.close(); }
**記得在打開文件的時(shí)候做異常處理哦。博主在這里就不改了,小伙伴們自己看看
上面的代碼呢,其實(shí)寫的非常的不好,尤其是在代碼復(fù)用的方面,不過,博主今天只是來舉個栗子,今后會更加注意,你們也要注意哦,上面是個反面教材向AI問一下細(xì)節(jié)
免責(zé)聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀點(diǎn)不代表本網(wǎng)站立場,如果涉及侵權(quán)請聯(lián)系站長郵箱:is@yisu.com進(jìn)行舉報(bào),并提供相關(guān)證據(jù),一經(jīng)查實(shí),將立刻刪除涉嫌侵權(quán)內(nèi)容。