迷宫问题——BFS
程序员文章站
2022-11-08 12:37:44
改进版 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; }