【C++板块提升计划】梦想护卫舰 第23关 逃离迷宫
本帖最后由 zhangjinxuan 于 2023-2-17 19:36 编辑上一关：组合数计算
梦想护卫舰 第23关 逃离迷宫
梦想护卫舰继续出发，可是，你们在航行中发现了不对劲
你们，被困在了一个 n 行 m 列的迷宫里面，而且迷宫每个格子的高度可能是不一的，甚至还有障碍物
也就是说，i 行 j 列的格子要么有一个高度 hi,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
输入格式
n m k
h1,1 h1,2 ... h1,m
h2,1 h2,2 ... h2,m
...
hn,1 hn,2 ... hn,m
x1 y1
x2 y2
...
xk yk
(xi, yi)表示第 i 个传送门的坐标
输出格式
一个整数，表示答案
输入样例1
4 4 2
1 2 3 4
1 2 3 4
1 2 3 4
1 2 3 4
1 1
3 4
输出样例1
3
输入样例2
4 4 3
1 2 3 4
1 2 3 4
1 2 3 4
1 2 3 4
1 1
2 4
4 1
输出样例2
4
输入样例3
2 5 0
1 0 3 3 4
2 3 4 0 5
输出样例3
7
输入样例4
4 4 3
1 1 1 0
1 1 0 1
1 0 1 1
0 1 1 1
1 1
2 1
3 3
输出样例4
3
输入输出样例5
见原题的附加文件
样例解释
请见原题
数据范围
https://cdn.luogu.com.cn/upload/image_hosting/f2epmv84.png
static/image/hrline/1.gif
注：本题非原创，选自洛谷，链接：https://www.luogu.com.cn/problem/P9065
static/image/hrline/1.gif
答案与解析
**** Hidden Message *****
最佳战士排行榜
|第一名|第二名|第三名
名字|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. 因为额度原因，部分鱼油可能下一天才能奖励。
static/image/hrline/1.gif
下一关：性能测试
创作不易，如果你喜欢，别忘了评分、顶{:10_281:}
本关满意度调查 抢一个沙发
(要是有回帖奖励就好了) 我也要回帖奖励 {:5_104:}感觉看懂题目比亲身从迷宫里走出来还要难 洋洋痒 发表于 2023-2-12 13:35
感觉看懂题目比亲身从迷宫里走出来还要难
看原题吧{:10_250:} zhangjinxuan 发表于 2023-2-12 13:37
看原题吧
{:10_266:}不是题目的原因，是我一看到这么长就已经晕了 洋洋痒 发表于 2023-2-12 13:45
不是题目的原因，是我一看到这么长就已经晕了
是啊，都讨厌长题目的{:10_291:} sfqxx 发表于 2023-2-12 12:54
抢一个沙发
(要是有回帖奖励就好了)
怎么……都觉得题目难？？？{:10_277:}
算了，过几天我出一道好（shui) 题吧{:10_284:} 来看看，我能加入吗？就是梦想护卫舰 myd0313 发表于 2023-2-13 21:08
来看看，我能加入吗？就是梦想护卫舰
需要中级鱼油以上才能加入哦~（没办法，谁让要好友限制呢） zhangjinxuan 发表于 2023-2-13 21:09
需要中级鱼油以上才能加入哦~（没办法，谁让要好友限制呢）
啊，这样啊 感觉这个bfs写的有点繁琐 myd0313 发表于 2023-2-13 21:09
啊，这样啊
加油吧~ 比较简单，来写一写：
#include<bits/stdc++.h>
using namespace std;
const int INF=0x3f3f3f3f;
int n,m,k,x,y,px,py,h,d1,d2,v,ans;
bool c;
int dx={0,1,0,-1};
int dy={-1,0,1,0};
int bfs(int bx,int by,int ex,int ey,int d[])
{
int ret=INF;
queue<pair<int,int> > q;
d=0;
for(q.push(make_pair(bx,by));!q.empty();q.pop())
{
x=q.front().first;
y=q.front().second;
if(ret==INF&&v) ret=d;
for(int i=0;i<4;i++)
{
px=x+dx;
py=y+dy;
if(px>0&&px<=n&&py>0&&py<=m&&h!=0&&d==INF)
{
d=d+1;
q.push(make_pair(px,py));
}
}
}
return ret;
}
int main()
{
cin>>n>>m>>k;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
scanf("%d",&h);
}
}
for(int i=1;i<=k;i++)
{
scanf("%d %d",&x,&y);
v=1;
}
memset(d1,0x3f3f3f3f,sizeof d1);
memset(d2,0x3f3f3f3f,sizeof d2);
int dis1=bfs(1,1,n,m,d1);
int dis2=bfs(n,m,1,1,d2);
ans=min(dis1+dis2+2,d1);
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
if(d1==dis1&&v) c]=1;
}
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
if(d2==dis2&&v)
{
if(c]) ans=min(ans,dis1+dis2+1);
}
}
}
if(ans==INF) ans=-1;
cout<<ans<<endl;
return 0;
} myd0313不是您小号吗？ sfqxx 发表于 2023-2-17 17:17
myd0313不是您小号吗？
恭喜猜对了{:10_266:}
要不今天我发，明天你发{:10_256:} zhangjinxuan 发表于 2023-2-17 18:07
恭喜猜对了
要不今天我发，明天你发
行 #include <bits/stdc++.h>
using namespace std;
const int maxn=3e3+10;
const int maxm=9e6+10;
const int inf=1e9;
const int dx={0,1,0,-1};
const int dy={-1,0,1,0};
#define pii pair<int,int>
#define mp make_pair
#define fi first
#define se second
int n,m,k;
int x,y,dis1,dis2,h;
int st1,ed1,st2,ed2;
int vis1,vis2;
inline bool valid(int x,int y)
{
if(x>=1 && x<=n && y>=1 && y<=m && h!=0)return 1;
return 0;
}
queue<pii> q;
inline void bfs1(int x0,int y0)
{
q.push(mp(x0,y0));
dis1=0;
vis1=1;
while(!q.empty())
{
int x2=q.front().fi,y2=q.front().se;
q.pop();
for(int i=0;i<4;i++)
{
int nx=x2+dx,ny=y2+dy;
if(!valid(nx,ny) || vis1)continue;
dis1=dis1+1;
vis1=1;
q.push(mp(nx,ny));
}
}
}
inline void bfs2(int x0,int y0)
{
q.push(mp(x0,y0));
dis2=0;
vis2=1;
while(!q.empty())
{
int x2=q.front().fi,y2=q.front().se;
q.pop();
for(int i=0;i<4;i++)
{
int nx=x2+dx,ny=y2+dy;
if(!valid(nx,ny) || vis2)continue;
dis2=dis2+1;
vis2=1;
q.push(mp(nx,ny));
}
}
}
bool flag=1;
int app;
int main()
{
scanf("%d%d%d",&n,&m,&k);
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)scanf("%d",&h);
}
for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)dis1=dis2=inf;
bfs1(1,1);bfs2(n,m);
if(dis1==inf)
{
puts("-1");
exit(0);
}
if(k<=1)
{
printf("%d\n",dis1);
exit(0);
}
for(int i=1;i<=k;i++)scanf("%d%d",&x,&y);
int min1=inf,min2=inf;
for(int i=1;i<=k;i++)
{
min1=min(min1,dis1]]);
min2=min(min2,dis2]]);
}
for(int i=1;i<=k;i++)
{
if(dis1]]==min1)app]]]=1;
}
for(int i=1;i<=k;i++)
{
if(dis2]]==min2 && app]]]==1)
{
flag=0;
break;
}
}
int ans=dis1;
ans=min(ans,min1+min2+flag+1);
printf("%d\n",ans);
return 0;
} sfqxx 发表于 2023-2-18 15:36
我*{:10_257:}
自 己 写 的{:10_257:} zhangjinxuan 发表于 2023-2-18 15:40
我*
自 己 写 的
真·自己写的{:5_98:}
页:
[1]
2