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

zhangjinxuan · 发表于 2023-2-12 12:48:21

本帖最后由 zhangjinxuan 于 2023-2-17 19:36 编辑

上一关：组合数计算

梦想护卫舰第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

输入格式

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

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

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

输入样例1

输出样例1

输入样例2

输出样例2

输入样例3

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

输出样例3

输入样例4

输出样例4

输入输出样例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

比较简单，来写一写：

#include<bits/stdc++.h>
using namespace std;
const int INF=0x3f3f3f3f;
int n,m,k,x,y,px,py,h[3001][3001],d1[3001][3001],d2[3001][3001],v[3001][3001],ans;
bool c[9000001];
int dx[4]={0,1,0,-1};
int dy[4]={-1,0,1,0};
int bfs(int bx,int by,int ex,int ey,int d[][3001])
{
        int ret=INF;
        queue<pair<int,int> > q;
        d[bx][by]=0;
        for(q.push(make_pair(bx,by));!q.empty();q.pop())
        {
                x=q.front().first;
                y=q.front().second;
                if(ret==INF&&v[x][y]) ret=d[x][y];
                for(int i=0;i<4;i++)
                {
                        px=x+dx[i];
                        py=y+dy[i];
                        if(px>0&&px<=n&&py>0&&py<=m&&h[px][py]!=0&&d[px][py]==INF)
                        {
                                d[px][py]=d[x][y]+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[i][j]); 
                }
        }
        for(int i=1;i<=k;i++)
        {
                scanf("%d %d",&x,&y);
                v[x][y]=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[n][m]);
        for(int i=1;i<=n;i++)
        {
                for(int j=1;j<=m;j++)
                {
                        if(d1[i][j]==dis1&&v[i][j]) c[h[i][j]]=1;
                }
        }
        for(int i=1;i<=n;i++)
        {
                for(int j=1;j<=m;j++)
                {
                        if(d2[i][j]==dis2&&v[i][j]) 
                        {
                                if(c[h[i][j]]) ans=min(ans,dis1+dis2+1);
                        }
                }
        }
        if(ans==INF) ans=-1;
        cout<<ans<<endl;
        return 0;
}

跳转到最佳答案楼层

sfqxx · 发表于 2023-2-12 12:54:15

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

liuhongrun2022 · 发表于 2023-2-12 13:11:19

我也要回帖奖励

洋洋痒 · 发表于 2023-2-12 13:35:14

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

zhangjinxuan · 发表于 2023-2-12 13:37:07

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

看原题吧

洋洋痒 · 发表于 2023-2-12 13:45:51

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

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

zhangjinxuan · 发表于 2023-2-12 13:50:27

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

是啊，都讨厌长题目的

zhangjinxuan · 发表于 2023-2-12 15:33:21

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

怎么……都觉得题目难？？？

算了，过几天我出一道好（shui) 题吧

myd0313 · 发表于 2023-2-13 21:08:15

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

zhangjinxuan · 发表于 2023-2-13 21:09:08

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

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

myd0313 · 发表于 2023-2-13 21:09:30

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

啊，这样啊

myd0313 · 发表于 2023-2-13 21:18:59

感觉这个bfs写的有点繁琐

zhangjinxuan · 发表于 2023-2-13 21:19:20

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

加油吧~

myd0313 · 发表于 2023-2-14 19:29:08

这个最佳答案由 myd0313 给出，感谢 myd0313 的回答。

单击隐藏图章

比较简单，来写一写：

#include<bits/stdc++.h>
using namespace std;
const int INF=0x3f3f3f3f;
int n,m,k,x,y,px,py,h[3001][3001],d1[3001][3001],d2[3001][3001],v[3001][3001],ans;
bool c[9000001];
int dx[4]={0,1,0,-1};
int dy[4]={-1,0,1,0};
int bfs(int bx,int by,int ex,int ey,int d[][3001])
{
        int ret=INF;
        queue<pair<int,int> > q;
        d[bx][by]=0;
        for(q.push(make_pair(bx,by));!q.empty();q.pop())
        {
                x=q.front().first;
                y=q.front().second;
                if(ret==INF&&v[x][y]) ret=d[x][y];
                for(int i=0;i<4;i++)
                {
                        px=x+dx[i];
                        py=y+dy[i];
                        if(px>0&&px<=n&&py>0&&py<=m&&h[px][py]!=0&&d[px][py]==INF)
                        {
                                d[px][py]=d[x][y]+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[i][j]); 
                }
        }
        for(int i=1;i<=k;i++)
        {
                scanf("%d %d",&x,&y);
                v[x][y]=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[n][m]);
        for(int i=1;i<=n;i++)
        {
                for(int j=1;j<=m;j++)
                {
                        if(d1[i][j]==dis1&&v[i][j]) c[h[i][j]]=1;
                }
        }
        for(int i=1;i<=n;i++)
        {
                for(int j=1;j<=m;j++)
                {
                        if(d2[i][j]==dis2&&v[i][j]) 
                        {
                                if(c[h[i][j]]) ans=min(ans,dis1+dis2+1);
                        }
                }
        }
        if(ans==INF) ans=-1;
        cout<<ans<<endl;
        return 0;
}

sfqxx · 发表于 2023-2-17 17:17:27

myd0313不是您小号吗？

zhangjinxuan · 发表于 2023-2-17 18:07:28

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

恭喜猜对了

要不今天我发，明天你发

sfqxx · 发表于 2023-2-17 18:44:17

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

要不今天我发，明天你发

行

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

#include <bits/stdc++.h>
using namespace std;
const int maxn=3e3+10;
const int maxm=9e6+10;
const int inf=1e9;
const int dx[4]={0,1,0,-1};
const int dy[4]={-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[maxm],y[maxm],dis1[maxn][maxn],dis2[maxn][maxn],h[maxn][maxn];
int st1,ed1,st2,ed2;
int vis1[maxn][maxn],vis2[maxn][maxn];
inline bool valid(int x,int y)
{
        if(x>=1 && x<=n && y>=1 && y<=m && h[x][y]!=0)return 1;
        return 0;
}
queue<pii> q;
inline void bfs1(int x0,int y0)
{
        q.push(mp(x0,y0));
        dis1[x0][y0]=0;
        vis1[x0][y0]=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[i],ny=y2+dy[i];
                        if(!valid(nx,ny) || vis1[nx][ny])continue;
                        dis1[nx][ny]=dis1[x2][y2]+1;
                        vis1[nx][ny]=1;
                        q.push(mp(nx,ny));
                }
        }
}
inline void bfs2(int x0,int y0)
{
        q.push(mp(x0,y0));
        dis2[x0][y0]=0;
        vis2[x0][y0]=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[i],ny=y2+dy[i];
                        if(!valid(nx,ny) || vis2[nx][ny])continue;
                        dis2[nx][ny]=dis2[x2][y2]+1;
                        vis2[nx][ny]=1;
                        q.push(mp(nx,ny));
                }
        }
}
bool flag=1;
int app[maxm];
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[i][j]);
        }
        for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)dis1[i][j]=dis2[i][j]=inf;
        bfs1(1,1);bfs2(n,m);
        if(dis1[n][m]==inf)
        {
                puts("-1");
                exit(0);
        }
        if(k<=1)
        {
                printf("%d\n",dis1[n][m]);
                exit(0);
        }
        for(int i=1;i<=k;i++)scanf("%d%d",&x[i],&y[i]);
        int min1=inf,min2=inf;
        for(int i=1;i<=k;i++)
        {
                min1=min(min1,dis1[x[i]][y[i]]);
                min2=min(min2,dis2[x[i]][y[i]]);
        }
        for(int i=1;i<=k;i++)
        {
                if(dis1[x[i]][y[i]]==min1)app[h[x[i]][y[i]]]=1;
        }
        for(int i=1;i<=k;i++)
        {
                if(dis2[x[i]][y[i]]==min2 && app[h[x[i]][y[i]]]==1)
                {
                        flag=0;
                        break;
                }
        }
        int ans=dis1[n][m];
        ans=min(ans,min1+min2+flag+1);
        printf("%d\n",ans);
        return 0;
}

zhangjinxuan · 发表于 2023-2-18 15:40:14

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

我*

自己写的

sfqxx · 发表于 2023-2-18 16:23:53

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

自己写的

真·自己写的

账号		自动登录	找回密码
密码			立即注册

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

评分

本帖被以下淘专辑推荐:

评分

评分

评分

评分

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