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

zhangjinxuan

上一关：组合数计算

梦想护卫舰 第23关 逃离迷宫

梦想护卫舰继续出发，可是，你们在航行中发现了不对劲

你们，被困在了一个 n 行 m 列的迷宫里面，而且迷宫每个格子的高度可能是不一的，甚至还有障碍物

也就是说，i 行 j 列的格子要么有一个高度 h_i,j，要么就是障碍物，不能通过（方便起见，障碍物格子就用 0 表示）

此外，还有 k 个格子有传送门，开始时，你在 (1, 1) 的位置，你要逃离迷宫，就得到达 (n, m) 的位置

你在任意方格 (i, j) 可以执行的操作如下：

• 上下左右移动，也就是移动到 (i+1, j), (i-1, j), (i, j+1), (i, j-1) 这四个方格之一，移动时不能碰到障碍物，也不能移出边界，但不受高度影响
• 如果方格 (i, j) 有传送门，则你可以传送至另一个同样有传送门且与方格 (i,j) 高度相等的方格上；
• 将当前格子的方格改为任一正整数
  

进行上述每项行动均需花费 1个单位时间，现在请问你掏出迷宫的最短花费时间是多少，如果不能逃出迷宫，请输出 -1

输入格式

1. n m k
   
2. h1,1 h1,2 ... h1,m
   
3. h2,1 h2,2 ... h2,m
   
4. ...
   
5. hn,1 hn,2 ... hn,m
   
6. x1 y1
   
7. x2 y2
   
8. ...
   
9. xk yk

复制代码

(x_i, y_i)表示第 i 个传送门的坐标

输出格式
一个整数，表示答案

输入样例1

1. 4 4 2
   
2. 1 2 3 4
   
3. 1 2 3 4
   
4. 1 2 3 4
   
5. 1 2 3 4
   
6. 1 1
   
7. 3 4

复制代码

输出样例1

1. 3

复制代码

输入样例2

1. 4 4 3
   
2. 1 2 3 4
   
3. 1 2 3 4
   
4. 1 2 3 4
   
5. 1 2 3 4
   
6. 1 1
   
7. 2 4
   
8. 4 1

复制代码

输出样例2

1. 4

复制代码

输入样例3

1. 2 5 0
   
2. 1 0 3 3 4
   
3. 2 3 4 0 5

复制代码

输出样例3

1. 7

复制代码

输入样例4

1. 4 4 3
   
2. 1 1 1 0
   
3. 1 1 0 1
   
4. 1 0 1 1
   
5. 0 1 1 1
   
6. 1 1
   
7. 2 1
   
8. 3 3

复制代码

输出样例4

1. 3

复制代码

输入输出样例5
见原题的附加文件

样例解释
请见原题

数据范围

                               
登录/注册后可看大图

                               
登录/注册后可看大图

注：本题非原创，选自洛谷，链接：https://www.luogu.com.cn/problem/P9065

                               
登录/注册后可看大图

答案与解析

游客，如果您要查看本帖隐藏内容请回复

[/hide]


最佳战士排行榜

	第一名	第二名	第三名
名字	myd0313
链接	戳我
语言	C++
代码得分	100
综合得分	100
奖励	5鱼币5荣誉+“最佳答案”	3鱼币3荣誉+"	2鱼币2荣誉

/*综合评分会参照运行时间（代码效率），代码长度，代码可读性，解题思路，代码得分等来进行评分*/

我们一起来 Hack

Hack 规则
1. Hack 经证实均有奖励，你在 Hack 时得提供完整证据、证明;
2. 在本关，仅支持标程 Hack，细节问题奖励 2~5 鱼币，重点问题奖励 5~10 鱼币
3. 奖励上限为 3 次

名字	等待着Hack大佬~
Hack 类型
是否证实
链接
奖励

答题/奖励规则
1. 不能抄题解，否则无奖励，可能还会扣分;
2. 当您遇到问题时，您可以回贴提问，我会为您解答
3. 提供完整能得分的题解，均有奖励。
4. 因为额度原因，部分鱼油可能下一天才能奖励。

                               
登录/注册后可看大图

下一关：性能测试

创作不易，如果你喜欢，别忘了评分、顶


本关满意度调查

最佳答案

月排行榜 / 总排行榜

myd0313

2023-2-14 19:29:08

比较简单，来写一写：

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. }

复制代码

跳转到最佳答案楼层

sfqxx

抢一个沙发
(要是有回帖奖励就好了)

liuhongrun2022

我也要回帖奖励

洋洋痒

感觉看懂题目比亲身从迷宫里走出来还要难

zhangjinxuan

洋洋痒 发表于 2023-2-12 13:35
感觉看懂题目比亲身从迷宫里走出来还要难

看原题吧

洋洋痒

zhangjinxuan 发表于 2023-2-12 13:37
看原题吧

不是题目的原因，是我一看到这么长就已经晕了

zhangjinxuan

洋洋痒 发表于 2023-2-12 13:45
不是题目的原因，是我一看到这么长就已经晕了

是啊，都讨厌长题目的

zhangjinxuan

sfqxx 发表于 2023-2-12 12:54
抢一个沙发
(要是有回帖奖励就好了)

怎么……都觉得题目难？？？
算了，过几天我出一道好（shui) 题吧

myd0313

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

zhangjinxuan

myd0313 发表于 2023-2-13 21:08
来看看，我能加入吗？就是梦想护卫舰

需要中级鱼油以上才能加入哦~（没办法，谁让要好友限制呢）

myd0313

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

啊，这样啊

myd0313

感觉这个bfs写的有点繁琐

zhangjinxuan

myd0313 发表于 2023-2-13 21:09
啊，这样啊

加油吧~

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. }

复制代码

sfqxx

myd0313不是您小号吗？

zhangjinxuan

sfqxx 发表于 2023-2-17 17:17
myd0313不是您小号吗？

恭喜猜对了

要不今天我发，明天你发

sfqxx

zhangjinxuan 发表于 2023-2-17 18:07
恭喜猜对了

要不今天我发，明天你发

行

sfqxx

1. #include <bits/stdc++.h>
   
2. using namespace std;
   
3. const int maxn=3e3+10;
   
4. const int maxm=9e6+10;
   
5. const int inf=1e9;
   
6. const int dx[4]={0,1,0,-1};
   
7. const int dy[4]={-1,0,1,0};
   
8. #define pii pair<int,int>
   
9. #define mp make_pair
   
10. #define fi first
    
11. #define se second
    
12. int n,m,k;
    
13. int x[maxm],y[maxm],dis1[maxn][maxn],dis2[maxn][maxn],h[maxn][maxn];
    
14. int st1,ed1,st2,ed2;
    
15. int vis1[maxn][maxn],vis2[maxn][maxn];
    
16. inline bool valid(int x,int y)
    
17. {
    
18.         if(x>=1 && x<=n && y>=1 && y<=m && h[x][y]!=0)return 1;
    
19.         return 0;
    
20. }
    
21. queue<pii> q;
    
22. inline void bfs1(int x0,int y0)
    
23. {
    
24.         q.push(mp(x0,y0));
    
25.         dis1[x0][y0]=0;
    
26.         vis1[x0][y0]=1;
    
27.         while(!q.empty())
    
28.         {
    
29.                 int x2=q.front().fi,y2=q.front().se;
    
30.                 q.pop();
    
31.                 for(int i=0;i<4;i++)
    
32.                 {
    
33.                         int nx=x2+dx[i],ny=y2+dy[i];
    
34.                         if(!valid(nx,ny) || vis1[nx][ny])continue;
    
35.                         dis1[nx][ny]=dis1[x2][y2]+1;
    
36.                         vis1[nx][ny]=1;
    
37.                         q.push(mp(nx,ny));
    
38.                 }
    
39.         }
    
40. }
    
41. inline void bfs2(int x0,int y0)
    
42. {
    
43.         q.push(mp(x0,y0));
    
44.         dis2[x0][y0]=0;
    
45.         vis2[x0][y0]=1;
    
46.         while(!q.empty())
    
47.         {
    
48.                 int x2=q.front().fi,y2=q.front().se;
    
49.                 q.pop();
    
50.                 for(int i=0;i<4;i++)
    
51.                 {
    
52.                         int nx=x2+dx[i],ny=y2+dy[i];
    
53.                         if(!valid(nx,ny) || vis2[nx][ny])continue;
    
54.                         dis2[nx][ny]=dis2[x2][y2]+1;
    
55.                         vis2[nx][ny]=1;
    
56.                         q.push(mp(nx,ny));
    
57.                 }
    
58.         }
    
59. }
    
60. bool flag=1;
    
61. int app[maxm];
    
62. int main()
    
63. {
    
64.         scanf("%d%d%d",&n,&m,&k);
    
65.         for(int i=1;i<=n;i++)
    
66.         {
    
67.                 for(int j=1;j<=m;j++)scanf("%d",&h[i][j]);
    
68.         }
    
69.         for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)dis1[i][j]=dis2[i][j]=inf;
    
70.         bfs1(1,1);bfs2(n,m);
    
71.         if(dis1[n][m]==inf)
    
72.         {
    
73.                 puts("-1");
    
74.                 exit(0);
    
75.         }
    
76.         if(k<=1)
    
77.         {
    
78.                 printf("%d\n",dis1[n][m]);
    
79.                 exit(0);
    
80.         }
    
81.         for(int i=1;i<=k;i++)scanf("%d%d",&x[i],&y[i]);
    
82.         int min1=inf,min2=inf;
    
83.         for(int i=1;i<=k;i++)
    
84.         {
    
85.                 min1=min(min1,dis1[x[i]][y[i]]);
    
86.                 min2=min(min2,dis2[x[i]][y[i]]);
    
87.         }
    
88.         for(int i=1;i<=k;i++)
    
89.         {
    
90.                 if(dis1[x[i]][y[i]]==min1)app[h[x[i]][y[i]]]=1;
    
91.         }
    
92.         for(int i=1;i<=k;i++)
    
93.         {
    
94.                 if(dis2[x[i]][y[i]]==min2 && app[h[x[i]][y[i]]]==1)
    
95.                 {
    
96.                         flag=0;
    
97.                         break;
    
98.                 }
    
99.         }
    
100.         int ans=dis1[n][m];
     
101.         ans=min(ans,min1+min2+flag+1);
     
102.         printf("%d\n",ans);
     
103.         return 0;
     
104. }

复制代码

zhangjinxuan

sfqxx 发表于 2023-2-18 15:36

我*

自 己 写 的

sfqxx

zhangjinxuan 发表于 2023-2-18 15:40
我*

自 己 写 的

真·自己写的