c++ 迷宫思路_迷宫问题求解——C++

- 日理万妓 2023-01-10 05:12 136阅读 0赞

迷宫问题思路

根据昨天的博客，有如下几种解决方案

克鲁斯卡尔 ，为避免死循环，需要设定优化路径的次数。

Prim，为避免死循环，需要设定优化路径的次数，暂定200次。

BFS ， 实现简单，无死循环。

DFS , 实现简单，无死循环，复杂度较低。

动态规划，实时根据权重调整方向，目前看来最合适的解决方案。需要以数据证明。

综上，本次优先选择BFS，首先不存在死循环的风险，其次算法复杂度较低，容易理解且实现。适合初步练手。

一. 思路及程序算法

首先建立迷宫，将其看作点位矩阵，先把墙堆起来，剩下的就是路。

而每个点都有四个方向(上、下、左、有)，每个方向上都对应一个点。在这四个点中，有一个点是当前站立点的“上一个点”，另外三个点是当前站立点的“下一个点”，如图1.1所示，红色框为当前站立点，蓝色框为“上一个点”，黄色框为三个“下一个点”。

![5a01086b44ec46a49ef74f2b3da0cfd5.png][]

图1.1站立点的四个方向

当前站立点有三种状态，分别是“终点”、“通路”和“死路”。如果当前站立点是“终点”，则停止搜索；如果当前站立点是“通路”，则向下继续走；如果当前站立点是“死路”，则要向回走，然后搜索其它路径。其流程如图1.2所示。

![6bb981c88d43b79d6a90699af514f34b.png][]

图1.2判断迷宫路径流程图

二. 实现

实现效果如图2.1所示：

![f4942a15f86d74535b5c689917cdedf4.png][]

图2.1 BFS迷宫求解实现图

BFS迷宫求解实现代码如下：

\#include

using namespace std;

\#define coordi(x,y) ( m\*(x-1)+y )

const int maxn = 30;

const int dx\[\] = \{0,0,1,-1\};

const int dy\[\] = \{1,-1,0,0\};

int mp\[maxn+10\]\[maxn+10\];

int nxtx\[maxn+10\]\[maxn+10\];

int nxty\[maxn+10\]\[maxn+10\];

bool vis\[maxn+10\]\[maxn+10\];

int fa\[(maxn+10)\*(maxn+10)\];

int n , m;

int stx , sty , edx , edy;

inline int check( int x , int y )

return 1<=x && x<=n && 1<=y && y<=m;

inline void print\_map()

puts("\\n==============================================");

for( int i = 1; i <= n; i++ )

for( int j = 1; j <= m; j++ )

printf("%c",mp\[i\]\[j\]);

putchar('\\n');

puts("==============================================");

// 并查集

int getfa( int x )

return x==fa\[x\]?x:fa\[x\] = getfa(fa\[x\]);

void unio( int a , int b )

int fx = getfa(a) , fy = getfa(b);

if ( fx != fy ) fa\[fx\] = fy;

// 并查集

void connect()

int t = n\*m/3\*2;

for( int i = 1; i <= n\*m; i++ ) fa\[i\] = i;

int fs = getfa(coordi(stx,sty)) , ft = getfa(coordi(edx,edy));

while( fs != ft || t > 0 )

t--;

int px = rand()%n+1 , py = rand()%m+1;

if ( mp\[px\]\[py\] == 'X' )

mp\[px\]\[py\] = '.';

for( int k = 0 ; k< 4; k++ )

int xx = px + dx\[k\] , yy = py + dy\[k\];

if ( check(xx,yy) && mp\[xx\]\[yy\] != 'X' ) unio( coordi(px,py) , coordi(xx,yy) );

fs = getfa(coordi(stx,sty)) , ft = getfa(coordi(edx,edy));

void init()

srand(time(0));

n = rand()%maxn+10;

m = rand()%maxn+10;

cout<

for( int i = 1; i <= n; i++ )

for( int j = 1; j <= m; j++ ) mp\[i\]\[j\] = 'X';

stx = rand()%n+1 , sty = rand()%m+1;

edx = rand()%n+1 , edy = rand()%m+1;

while( abs(edx-stx) + abs(edy-sty) <= 1 ) edx = rand()%n+1 , edy = rand()%m+1;

mp\[stx\]\[sty\] = 'S' , mp\[edx\]\[edy\] = 'T';

cout<

connect();

print\_map();

void print\_path() // path = '\*' st = S , ed = T , road = . , wall = X

int x = edx , y = edy;

while( !( x == stx && y == sty ) )

mp\[x\]\[y\] = '\*';

int tx = nxtx\[x\]\[y\];

y = nxty\[x\]\[y\];

x = tx;

mp\[edx\]\[edy\] = 'T';

print\_map();

void bfs()

queue< pair > q;

q.push( make\_pair(stx,sty) );

memset(vis,0,sizeof(vis));

vis\[stx\]\[sty\] = true;

while( !q.empty() )

pair temp = q.front();

q.pop();

if ( temp.first == edx && temp.second == edy )

print\_path();

return;

for( int k = 0; k < 4; k++ )

int xx = temp.first + dx\[k\] , yy = temp.second + dy\[k\];

if ( !check(xx,yy) || vis\[xx\]\[yy\] || mp\[xx\]\[yy\] == 'X' ) continue;

vis\[xx\]\[yy\] = 1 , nxtx\[xx\]\[yy\] = temp.first , nxty\[xx\]\[yy\] = temp.second;

q.push( make\_pair(xx,yy) );

int main()

init();

bfs();

return 0;

[5a01086b44ec46a49ef74f2b3da0cfd5.png]: /images/20221119/a28cf4fe32f9498699bcfb0ab48e6734.png
[6bb981c88d43b79d6a90699af514f34b.png]: /images/20221119/cd6acbf7d5504a418288acea2c9845bd.png
[f4942a15f86d74535b5c689917cdedf4.png]: /images/20221119/af159eb7de2c42768d020bdb5280554d.png