題目鏈接：https://nanti.jisuanke.com/t/43124
很SB的一個(gè)題目。不知道錯(cuò)在了哪兒。。
代碼是參考網(wǎng)上的一個(gè)代碼：

#include<bits/stdc++.h>using namespace std;#define ll long long#define N 1010#define inf 0x3f3f3f3fchar g[N][1010];//地圖int com[N][N] = { 0 };//用來標(biāo)記是否為傳送門int door[N][3] = { 0 };//用來記錄傳送到哪door[i][0]和door[i][1]分別用來x,yint vis[N][N];//當(dāng)?shù)竭@一點(diǎn)時(shí)所用的花費(fèi)int dir[2][4] = { -1,+1,0,0,0,0,-1,+1 };int x, y;int n, m;int ans = inf;struct node{int x, y, num;};int bfs(int p, int q){queue<node>que;node w;w.x = p, w.y = q, w.num = 0;vis[p][q] = 0;que.push(w);while (!que.empty()){node w;w = que.front();que.pop();int pp = w.x, qq = w.y;//cout<<"sjbd "<<pp<<" "<<qq<<" "<<w.num<<endl;if(pp==x&&qq==y){return w.num;}int u = com[pp][qq];// cout<<"u="<<u<<endl;if (u != 0){int ppp = door[u][0];int qqq = door[u][1];if (g[ppp][qqq] == '.'&&w.num<vis[ppp][qqq]){//傳送到的點(diǎn)不是障礙且比較這么走的花費(fèi)小vis[ppp][qqq] = w.num;node e = w;e.x = ppp, e.y = qqq;que.push(e);}}else{for (int i = 0; i < 4; i++){int xx = w.x+dir[0][i], yy = w.y+dir[1][i];if (vis[xx][yy]>w.num+1&& g[xx][yy] =='.'&&xx >= 1 && xx <= n && yy >= 1 && yy <= m){// cout << xx << " " << yy << endl;node e=w;e.num += 1;e.x = xx, e.y = yy;vis[xx][yy] = w.num+1;que.push(e);}}}}return inf; }int main(){ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);fill(vis[0],vis[0]+(N*N),inf);cin >> n >> m;for (int i = 1; i <= n; i++){for (int j = 1; j <= m; j++)cin >> g[i][j];}int p;cin >> p;while (p--){int x1, y1, x2, y2;cin >> x1 >> y1 >> x2 >> y2;com[x1][y1] = p+1;//因?yàn)镻值不會(huì)重復(fù)，所以可以用來標(biāo)記是否為傳送門的同時(shí)可以同時(shí)看他所傳送到的地方door[p+1][0] = x2;door[p+1][1] = y2;}cin >> x >> y;ans=bfs(1, 1);if(ans!=inf)cout<<ans<<endl;elsecout<<"No solution"<<endl;return 0; }

記憶化搜索顯示空間超限，不知道為什么。希望路過的大佬幫忙看一哈。。或者有沒有dfs做出來的大佬。。

#include<bits/stdc++.h> #define ll long long #define inf 0x3f3f3f3f using namespace std;const int maxx=1e3+100; int vs[maxx][maxx]; int mp[101][3]; char s[maxx][maxx]; int dp[maxx][maxx]; int d[][2]={{0,1},{1,0},{0,-1},{-1,0}}; int n,m,p,X,Y;inline void init() {memset(dp,inf,sizeof(dp));memset(s,'\0',sizeof(s)); } inline int dfs(int x,int y) {if(x==X&&y==Y) return dp[X][Y]=0;if(dp[x][y]!=inf) return dp[x][y];if(s[x][y]=='*') return dp[x][y]=inf;if(vs[x][y]) {int tx=mp[vs[x][y]][0];int ty=mp[vs[x][y]][1];dp[x][y]=dfs(tx,ty);return dp[x][y];}for(int i=0;i<4;i++){int tx=x+d[i][0];int ty=y+d[i][1];if(tx<0||tx>=n||ty<0||ty>=m||s[tx][ty]=='*') continue;dp[x][y]=min(dp[x][y],dfs(tx,ty)+1);}return dp[x][y]; } int main() {scanf("%d%d",&n,&m);init();for(int i=0;i<n;i++) scanf("%s",s[i]);scanf("%d",&p);int a,b,c,d;for(int i=1;i<=p;i++){scanf("%d%d%d%d",&a,&b,&c,&d);a-=1,b-=1,c-=1,d-=1;vs[a][b]=i;mp[i][0]=c;mp[i][1]=d;}scanf("%d%d",&X,&Y);X-=1,Y-=1;dp[X][Y]=0;dfs(0,0);if(dp[0][0]<inf) cout<<dp[0][0]<<endl;else cout<<"No solution"<<endl;return 0; }

努力加油a啊，(^o)/~

總結(jié)

以上是生活随笔為你收集整理的迷宫(BFS)的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。