[已解决]【C++板块提升计划】梦想护卫舰 第23关 逃离迷宫

myd0313

来看看，我能加入吗？就是梦想护卫舰

myd0313

zhangjinxuan 发表于 2023-2-13 21:09
需要中级鱼油以上才能加入哦~（没办法，谁让要好友限制呢）

啊，这样啊

myd0313

感觉这个bfs写的有点繁琐

myd0313

比较简单，来写一写：

1. #include<bits/stdc++.h>
   
2. using namespace std;
   
3. const int INF=0x3f3f3f3f;
   
4. int n,m,k,x,y,px,py,h[3001][3001],d1[3001][3001],d2[3001][3001],v[3001][3001],ans;
   
5. bool c[9000001];
   
6. int dx[4]={0,1,0,-1};
   
7. int dy[4]={-1,0,1,0};
   
8. int bfs(int bx,int by,int ex,int ey,int d[][3001])
   
9. {
   
10.         int ret=INF;
    
11.         queue<pair<int,int> > q;
    
12.         d[bx][by]=0;
    
13.         for(q.push(make_pair(bx,by));!q.empty();q.pop())
    
14.         {
    
15.                 x=q.front().first;
    
16.                 y=q.front().second;
    
17.                 if(ret==INF&&v[x][y]) ret=d[x][y];
    
18.                 for(int i=0;i<4;i++)
    
19.                 {
    
20.                         px=x+dx[i];
    
21.                         py=y+dy[i];
    
22.                         if(px>0&&px<=n&&py>0&&py<=m&&h[px][py]!=0&&d[px][py]==INF)
    
23.                         {
    
24.                                 d[px][py]=d[x][y]+1;
    
25.                                 q.push(make_pair(px,py));
    
26.                         }
    
27.                 }
    
28.         }
    
29.         return ret;
    
30. }
    
31. int main()
    
32. {
    
33.         cin>>n>>m>>k;
    
34.         for(int i=1;i<=n;i++)
    
35.         {
    
36.                 for(int j=1;j<=m;j++)
    
37.                 {
    
38.                         scanf("%d",&h[i][j]);
    
39.                 }
    
40.         }
    
41.         for(int i=1;i<=k;i++)
    
42.         {
    
43.                 scanf("%d %d",&x,&y);
    
44.                 v[x][y]=1;
    
45.         }
    
46.         memset(d1,0x3f3f3f3f,sizeof d1);
    
47.         memset(d2,0x3f3f3f3f,sizeof d2);
    
48.         int dis1=bfs(1,1,n,m,d1);
    
49.         int dis2=bfs(n,m,1,1,d2);
    
50.     ans=min(dis1+dis2+2,d1[n][m]);
    
51.         for(int i=1;i<=n;i++)
    
52.         {
    
53.                 for(int j=1;j<=m;j++)
    
54.                 {
    
55.                         if(d1[i][j]==dis1&&v[i][j]) c[h[i][j]]=1;
    
56.                 }
    
57.         }
    
58.         for(int i=1;i<=n;i++)
    
59.         {
    
60.                 for(int j=1;j<=m;j++)
    
61.                 {
    
62.                         if(d2[i][j]==dis2&&v[i][j])
    
63.                         {
    
64.                                 if(c[h[i][j]]) ans=min(ans,dis1+dis2+1);
    
65.                         }
    
66.                 }
    
67.         }
    
68.         if(ans==INF) ans=-1;
    
69.         cout<<ans<<endl;
    
70.         return 0;
    
71. }

复制代码