求迷宫通路问题
本次我们探讨一下迷宫小游戏。
目前创新互联已为上千家的企业提供了网站建设、域名、网页空间、绵阳服务器托管、企业网站设计、黎川网站维护等服务,公司将坚持客户导向、应用为本的策略,正道将秉承"和谐、参与、激情"的文化,与客户和合作伙伴齐心协力一起成长,共同发展。
让我们来探讨一下怎样可以得到一条通路,采用栈来实现。
当是通路的时候,节点压栈。当走到尽头不通时,出栈,寻找交叉口,寻找通路。
像这样在第一行存放迷宫的规格(在这里为传参少,定义正方形迷宫),设计迷宫,将迷宫以.txt格式存放在目录下(可以是任何地方,下文以默认路径为例)。
假设入口为(2,0),出口为迷宫最后一行任意位置。
MAZE.h
#pragma once #define _CRT_SECURE_NO_WARNINGS 1 #includeusing namespace std; #include #include class Pos //迷宫每一点的坐标 { public: Pos(int row,int col) :_row(row) , _col(col) {} int _row; int _col; }; void PrintPos(Pos& pos)// 打印节点坐标 { cout << "(" << pos._row << ", " << pos._col << ") "; } int* GetMaze(int& N)//从文件中打开迷宫 { FILE *font = fopen("maze.txt", "r"); assert(font != NULL);//打不开迷宫文件无意义 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) //判断是否为终点:设迷宫终点为能到达迷宫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) //寻找通路 { //若某一位置节点为0,进行压栈,且将数据改为2,寻找此节点上下左右位置为0的节点,再进行压栈, //若某一位置上下左右没有为0的节点,就出栈寻找上一个节点上下左右为0的节点进行压栈 assert(a); Pos top = paths.top(); a[top._row*N + top._col] = 2; while (!IsOverScope(paths.top(), N))//每次都要判断坐标是否越界、还要考虑出口旁边也是出口的情况就会多走几次 { //判断是否到达出口 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())//从上左右出来 return false; } void PrintPath(stack paths) //打印通路 { //最少Paths中有一个元素enrty在最底层 assert(!paths.empty()); cout << "通路: " << endl;; while (!paths.empty()) { PrintPos(paths.top()); paths.pop(); } cout << endl; }
test.cpp
#include"MAZE.h" void test() { //假设迷宫为N*N型正方形 int N = 0; int *a = GetMaze(N); PrintMaze(a, N); Pos enrty(2,0); stackpaths; 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; }
让我们来看看运行结果。
再试试将最后一行的‘0’改为1,让它变成无通路的迷宫
我们可以在思考一下:
当有好几条通路的时候,我们可以得到最短路吗?
我们可以得到以下思路:
记录最小路的步数 ,到达出口时将出口变为1 ,寻找下一条出口,然后更新最短路.
若要寻找这条最短路,那就可以在寻找一次,当通路的步数与最短路步数一致时输出通路。
但是上述方法存在很大的问题:虽然可以得到一个结果,但是不能够保证就是最短的。
因为,当按照上述编程寻找通路的逻辑 “上右下左” 顺序寻找通路时,就可能会把另一条更短的通路堵住,从而影响最短路的结果。
那到底怎么做呢? 期待下一篇博客。
网页标题:求迷宫通路问题
网页链接:http://scyanting.com/article/ppiigj.html