迷宫问题——BFS
程序员文章站
2022-03-12 18:13:26
改进版 BFS cpp 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 ......
改进版
###BFS
#include <bits/stdc++.h> 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<<"map size : "<<n<<" * "<<m<<endl; 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<<"start:("<<stx<<","<<sty<<")"<<endl; cout<<"end:("<<edx<<","<<edy<<")"<<endl; 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<int,int> > q; q.push( make_pair(stx,sty) ); memset(vis,0,sizeof(vis)); vis[stx][sty] = true; while( !q.empty() ) { pair<int,int> 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; }
推荐阅读
-
关于case when语句的报错问题详解
-
俗话说入乡随俗 清朝是怎么解决西洋人见皇帝不下跪的问题的
-
怎么解决MySQL密码问题
-
解决linux系统中运行node进程却无法杀死进程的问题
-
使用nginx代理gogs遇到推送代码错误的问题(RPC failed; HTTP 413 curl 22 The requested URL returned error: 413)
-
来探讨一下最近面试问的ThreadLocal问题
-
c# String扩展 让你在PadLeft和PadRight时不再受单双字节问题困扰
-
MFC连接数据库时,无法启动程序,计算机丢失libmysql.dll的问题解决办法
-
记录一下使用sea.js时遇到的几个小问题
-
Android RadioGroup多行显示效果 解决单选问题