2023-07-18力扣今日二题-太难了吧

这篇具有很好参考价值的文章主要介绍了2023-07-18力扣今日二题-太难了吧。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

链接:

LCP 75. 传送卷轴

题意:

给一个正方形迷宫,主角是A,每次可以上下左右走一格子,有四种类型的格子:墙、初始位置、魔法水晶、空地

另一个人B,可以传送一次A,只能在空地传送(墙、初始位置、魔法水晶位置不能传送)

传送会将A传送到水平或者竖直的镜像位置,且目标不得为墙壁(如果两种镜像位置都是墙则不能传送)

传送后,A到终点的最小距离,如果无法到达,返回-1

两个人都聪明绝顶

传送门:

两个普通的合法检查函数,脑子晕了没去简化,还用了两种坐标格式

两个镜像位置获取函数

一个BFS来记录每个格子到终点的距离,只要是方便计算传送后的距离,类似洪水填充寻路(MC水桶)

一个遍历获取传送后的距离,通过BFS得出的距离和两个翻转函数,存储在Mirror二维容器

先来一个优先队列排序用结构体

计算答案的函数

负责会传答案和初始化地图的工具人函数

碎碎念:

昨天摇到的困难题,昨晚在床上辗转反侧终于有了一点头猪,写完每日一题冲了一下,也就亿点点难

2023-07-18力扣今日二题-太难了吧,力扣每日一题,leetcode,算法,数据结构

最终还是去看了一下大佬代码,又是打卡题上的老pong右,优先队列哇,修修补补好歹是过了,就是有点惨不忍睹
2023-07-18力扣今日二题-太难了吧,力扣每日一题,leetcode,算法,数据结构

解:

这边来进入正题,先来看一个题目给的条件,如果无法到达,返回 -1,同时B的目标是阻止A到达终点以,如果存在一张地图A不通过传送无法到达终点,那么B就不会传送A,BUT还有一条条件:如果无法阻止,则尽可能 增加 A传送后到达终点的距离。那么即使传送完剩下的距离小于传送前剩下的距离,B也会传送,我就是这里又WA了两次,比如"S....T...",结果是2(其他格子都是墙)

代码很长,边看边聊:

两个普通的合法检查函数,脑子晕了没去简化,还用了两种坐标格式

bool check(const int& n,const int& m,const int& lg)//坐标合法检查 
{
    if(n<0||m<0) return false;
    if(n>=lg||m>=lg) return false;
    return true;
}
bool check(const pair<int,int>& pa,const int& lg)//坐标合法检查 
{
    const int n=pa.first,m=pa.second;
    if(n<0||m<0) return false;
    if(n>=lg||m>=lg) return false;
    return true;
}

两个镜像位置获取函数

inline pair<int,int> colMirror(const int& n,const int& m,const int& lg)//左右镜像-列镜像 
{
    return {n,lg-m-1};
}
inline pair<int,int> rowMirror(const int& n,const int& m,const int& lg)//上下镜像-行镜像 
{
    return {lg-n-1,m};
}

一个BFS来记录每个格子到终点的距离,只要是方便计算传送后的距离,类似洪水填充寻路(MC水桶)

void BFS_Distance(vector<vector<int>>& mp,const pair<int,int>& point,const int& lg)//类似洪水填充 
{
    vector<pair<int,int>>now{point};//当前坐标 
    while(true)
    {
        vector<pair<int,int>>next;//下一轮坐标 
        for(auto pa:now)
        {
            int nowx=pa.first,nowy=pa.second,nowval=mp[nowx][nowy];
            if(check(nowx-1,nowy,lg) && mp[nowx-1][nowy]==INT_MAX)//空地-初始位置
            {
                mp[nowx-1][nowy]=nowval+1;//更新距离
                next.push_back(pair<int,int>{nowx-1,nowy});
            }
            if(check(nowx+1,nowy,lg) && mp[nowx+1][nowy]==INT_MAX)//空地-初始位置
            {
                mp[nowx+1][nowy]=nowval+1;//更新距离
                next.push_back(pair<int,int>{nowx+1,nowy});
            }
            if(check(nowx,nowy-1,lg) && mp[nowx][nowy-1]==INT_MAX)//空地-初始位置
            {
                mp[nowx][nowy-1]=nowval+1;//更新距离
                next.push_back(pair<int,int>{nowx,nowy-1});
            }
            if(check(nowx,nowy+1,lg) && mp[nowx][nowy+1]==INT_MAX)//空地-初始位置
            {
                mp[nowx][nowy+1]=nowval+1;//更新距离
                next.push_back(pair<int,int>{nowx,nowy+1});
            }
        }
        now=next;
        if(now.empty()) break;
    }
}

一个遍历获取传送后的距离,通过BFS得出的距离和两个翻转函数,存储在Mirror二维容器

void BL_Mirror(vector<vector<int>>& Mirror,vector<vector<int>>& mp,
                    const int& lg,const pair<int,int>& start,const pair<int,int>& end)
{
    for(int i=0;i<lg;i++)
    {
        for(int j=0;j<lg;j++)
        {
            if(i==start.first && j==start.second)//起点
            {
                Mirror[i][j]=0;
                continue;
            } 
            if(i==end.first && j==end.second)//终点
            {
                Mirror[i][j]=0;
                continue;
            } 
            if(mp[i][j]==-2)//墙
            {
                Mirror[i][j]=-2;
                continue;
            }
            
            pair<int,int>Mp=colMirror(i,j,lg);int temp=0;//无法传送则为0
            if(check(Mp,lg) && mp[Mp.first][Mp.second]!=-2) temp=max(temp,mp[Mp.first][Mp.second]);//行列镜像选最大
            Mp=rowMirror(i,j,lg);
            if(check(Mp,lg) && mp[Mp.first][Mp.second]!=-2) temp=max(temp,mp[Mp.first][Mp.second]);//行列镜像选最大
            Mirror[i][j]=temp;
        }
    }
}

最后的重头戏,求答案,前面已经求出了传送后的距离,那么A只要选择一条路径上最大的值最小的路径就可以了,因为B肯定在A选的这条路径上的最大值位置进行传送,所以每条路径的值是这条路径中的最大值,A则要选一条值最小的路径

本来~~(可以不看这行)~~用类似Prim算法(最小生成树算法,每次选最小点加入点集)的方式,从起点出发,每次选择相邻的最小的格子加入集合,直到没有格子能加入或者终点加入集合,TLE了,修修改改降不下时间复杂度,只能乖乖看大佬代码

先来一个优先队列排序用结构体

struct cmp1
{
    bool operator ()(const pair<int,pair<int,int>>& L,const pair<int,pair<int,int>>& R)
    {
        return L.first>R.first;
    }
};

大佬用了一个优先队列,存储三个整形数据:格子的传送后距离,格子的横坐标X和格子的纵坐标Y。

排序规则就是上面这个:按照最小的传送后距离优先排序,然后也是从起点开始,每次选集合里传送后距离最小的格子(然后要抛弃掉),上下左右延伸一个,然后新格子的传送值是MAX(自己,旧格子),因为路径上的值实际上是路径中的最大值,而且由于每次是选集合里传送后距离最小的格子,且每次选完会用bool标记防止重复选取,所以传送后距离最小的格子优先延伸保证格子首先遇到的是它能遇到的最小的格子

计算答案的函数

void BFS_ans(vector<vector<int>>& Mirror,vector<vector<int>>& mp,
                    const int& lg,const pair<int,int>& start,const pair<int,int>& end)
{
    vector<pair<int,int>>move{{1,0},{-1,0},{0,1},{0,-1}};//四种移动方式 
    int ans=0;//什么都不是 
    vector<vector<bool>> book (lg,vector<bool>(lg,false)); //防止重复选择 
    priority_queue< pair<int,pair<int,int>> ,vector<pair<int,pair<int,int>>>, cmp1>nows;//绝中绝 
    nows.push({0,start});//起点开始 
    book[start.first][start.second]=1;//记录 
    while(!nows.empty())
    {
        pair<int,pair<int,int>>bignow=nows.top();nows.pop();
        pair<int,int>now=bignow.second;
        int nowx=now.first,nowy=now.second;//当前坐标 
        //cout<<"now"<<nowx<<" "<<nowy<<endl;
        for(auto pii:move)
        {
            int xx=nowx+pii.first,yy=nowy+pii.second;//移动后坐标 
            //cout<<xx<<"and"<<yy<<endl;
            if(check(xx,yy,lg) && book[xx][yy]==0 && Mirror[xx][yy]!=-2)
            {
                //cout<<xx<<"and"<<yy<<endl;
                //if(mp[xx][yy]>Mirror[xx][yy]) Mirror[xx][yy]=0;
                Mirror[xx][yy]=max(Mirror[xx][yy],Mirror[nowx][nowy]);
                nows.push({Mirror[xx][yy],{xx,yy}});
                book[xx][yy]=1;
            }
        }
        //cout<<"push"<<" val:"<<temp<<endl;
    }
}

负责会传答案和初始化地图的工具人函数

int challengeOfTheKeeper(vector<string>& maze)
{
    int lg=maze.size(),ans=0;//长度答案 
    pair<int,int>start,end;//起点 终点 
    vector<vector<int>>mp (lg,vector<int>(lg));
    vector<vector<int>>Mirror (lg,vector<int>(lg));
    
    for(int index=0;index<lg;index++)
    {
        for(int jndex=0;jndex<lg;jndex++)
        {
            if(maze[index][jndex]=='.') mp[index][jndex]=INT_MAX;//空地 int INT_MAX
            if(maze[index][jndex]=='#') mp[index][jndex]=-2;//墙壁 int -2
            if(maze[index][jndex]=='S')//初始位置 int INT_MAX
            {
                start.first=index;start.second=jndex;
                mp[index][jndex]=INT_MAX;
            }
            if(maze[index][jndex]=='T')//终点 int 0
            {
                end.first=index;end.second=jndex;
                mp[index][jndex]=0;
            }
        }
    }//更改地图存储方式
    BFS_Distance(mp,end,lg);//BFS更新距离
    BL_Mirror(Mirror,mp,lg,start,end);//遍历更新传送后距离 
    if(mp[start.first][start.second]==INT_MAX) return -1;
    BFS_ans(Mirror,mp,lg,start,end);//BFS获取答案
    
    /*cout<<"Mirror"<<endl;
    for(auto &i:Mirror)
    {
        for(auto &j:i)
        {
            printf("%02d ",j);
        }
        cout<<endl;
    }*/
    if(Mirror[end.first][end.second]==INT_MAX) return -1;
    else return Mirror[end.first][end.second];
}

可有可无的IDE里测试用main函数

int main()
{
    vector<string> maze;string s;
    while(cin>>s)
    {
        maze.push_back(s);
    }
    int ans=challengeOfTheKeeper(maze);
    cout<<ans<<endl;
    return 0;
}

实际代码:

#include<bits/stdc++.h>
using namespace std;
struct cmp1
{
    bool operator ()(const pair<int,pair<int,int>>& L,const pair<int,pair<int,int>>& R)
    {
        return L.first>R.first;
    }
};
bool check(const int& n,const int& m,const int& lg)//×ø±êºÏ·¨¼ì²é 
{
    if(n<0||m<0) return false;
    if(n>=lg||m>=lg) return false;
    return true;
}
bool check(const pair<int,int>& pa,const int& lg)//×ø±êºÏ·¨¼ì²é 
{
    const int n=pa.first,m=pa.second;
    if(n<0||m<0) return false;
    if(n>=lg||m>=lg) return false;
    return true;
}
inline pair<int,int> colMirror(const int& n,const int& m,const int& lg)//×óÓÒ¾µÏñ-ÁоµÏñ 
{
    return {n,lg-m-1};
}
inline pair<int,int> rowMirror(const int& n,const int& m,const int& lg)//ÉÏϾµÏñ-ÐоµÏñ 
{
    return {lg-n-1,m};
}
void BFS_Distance(vector<vector<int>>& mp,const pair<int,int>& point,const int& lg)//ÀàËƺéË®Ìî³ä 
{
    vector<pair<int,int>>now{point};//µ±Ç°×ø±ê 
    while(true)
    {
        vector<pair<int,int>>next;//ÏÂÒ»ÂÖ×ø±ê 
        for(auto pa:now)
        {
            int nowx=pa.first,nowy=pa.second,nowval=mp[nowx][nowy];
            if(check(nowx-1,nowy,lg) && mp[nowx-1][nowy]==INT_MAX)//¿ÕµØ-³õʼλÖÃ
            {
                mp[nowx-1][nowy]=nowval+1;//¸üоàÀë
                next.push_back(pair<int,int>{nowx-1,nowy});
            }
            if(check(nowx+1,nowy,lg) && mp[nowx+1][nowy]==INT_MAX)//¿ÕµØ-³õʼλÖÃ
            {
                mp[nowx+1][nowy]=nowval+1;//¸üоàÀë
                next.push_back(pair<int,int>{nowx+1,nowy});
            }
            if(check(nowx,nowy-1,lg) && mp[nowx][nowy-1]==INT_MAX)//¿ÕµØ-³õʼλÖÃ
            {
                mp[nowx][nowy-1]=nowval+1;//¸üоàÀë
                next.push_back(pair<int,int>{nowx,nowy-1});
            }
            if(check(nowx,nowy+1,lg) && mp[nowx][nowy+1]==INT_MAX)//¿ÕµØ-³õʼλÖÃ
            {
                mp[nowx][nowy+1]=nowval+1;//¸üоàÀë
                next.push_back(pair<int,int>{nowx,nowy+1});
            }
        }
        now=next;
        if(now.empty()) break;
    }
    /*cout<<"Distance"<<endl;
    for(auto &i:mp)
    {
        for(auto &j:i)
        {
            printf("%02d ",j);
        }
        cout<<endl;
    }*/
}
void BL_Mirror(vector<vector<int>>& Mirror,vector<vector<int>>& mp,
                    const int& lg,const pair<int,int>& start,const pair<int,int>& end)
{
    for(int i=0;i<lg;i++)
    {
        for(int j=0;j<lg;j++)
        {
            if(i==start.first && j==start.second)//Æðµã
            {
                Mirror[i][j]=0;
                continue;
            } 
            if(i==end.first && j==end.second)//ÖÕµã
            {
                Mirror[i][j]=0;
                continue;
            } 
            if(mp[i][j]==-2)//ǽ
            {
                Mirror[i][j]=-2;
                continue;
            }
            
            pair<int,int>Mp=colMirror(i,j,lg);int temp=0;
            if(check(Mp,lg) && mp[Mp.first][Mp.second]!=-2) temp=max(temp,mp[Mp.first][Mp.second]);//ÐÐÁоµÏñÑ¡×î´ó
            Mp=rowMirror(i,j,lg);
            if(check(Mp,lg) && mp[Mp.first][Mp.second]!=-2) temp=max(temp,mp[Mp.first][Mp.second]);//ÐÐÁоµÏñÑ¡×î´ó
            Mirror[i][j]=temp;
        }
    }
    /*cout<<"Mirror"<<endl;
    for(auto &i:Mirror)
    {
        for(auto &j:i)
        {
            printf("%02d ",j);
        }
        cout<<endl;
    }*/
}
void BFS_ans(vector<vector<int>>& Mirror,vector<vector<int>>& mp,
                    const int& lg,const pair<int,int>& start,const pair<int,int>& end)
{
    vector<pair<int,int>>move{{1,0},{-1,0},{0,1},{0,-1}};
    int ans=0;
    vector<vector<bool>> book (lg,vector<bool>(lg,false)); 
    priority_queue< pair<int,pair<int,int>> ,vector<pair<int,pair<int,int>>>, cmp1>nows;
    nows.push({0,start});
    book[start.first][start.second]=1;
    while(!nows.empty())
    {
        pair<int,pair<int,int>>bignow=nows.top();nows.pop();
        pair<int,int>now=bignow.second;
        int nowx=now.first,nowy=now.second;
        //cout<<"now"<<nowx<<" "<<nowy<<endl;
        for(auto pii:move)
        {
            int xx=nowx+pii.first,yy=nowy+pii.second;
            //cout<<xx<<"and"<<yy<<endl;
            if(check(xx,yy,lg) && book[xx][yy]==0 && Mirror[xx][yy]!=-2)
            {
                //cout<<xx<<"and"<<yy<<endl;
                //if(mp[xx][yy]>Mirror[xx][yy]) Mirror[xx][yy]=0;
                Mirror[xx][yy]=max(Mirror[xx][yy],Mirror[nowx][nowy]);
                nows.push({Mirror[xx][yy],{xx,yy}});
                book[xx][yy]=1;
            }
        }
        //cout<<"push"<<" val:"<<temp<<endl;
    }
}
int challengeOfTheKeeper(vector<string>& maze)
{
    int lg=maze.size(),ans=0;//³¤¶È´ð°¸ 
    pair<int,int>start,end;//Æðµã ÖÕµã 
    vector<vector<int>>mp (lg,vector<int>(lg));
    vector<vector<int>>Mirror (lg,vector<int>(lg));
    
    for(int index=0;index<lg;index++)
    {
        for(int jndex=0;jndex<lg;jndex++)
        {
            if(maze[index][jndex]=='.') mp[index][jndex]=INT_MAX;//¿ÕµØ int INT_MAX
            if(maze[index][jndex]=='#') mp[index][jndex]=-2;//ǽ±Ú int -2
            if(maze[index][jndex]=='S')//³õʼλÖà int INT_MAX
            {
                start.first=index;start.second=jndex;
                mp[index][jndex]=INT_MAX;
            }
            if(maze[index][jndex]=='T')//ÖÕµã int 0
            {
                end.first=index;end.second=jndex;
                mp[index][jndex]=0;
            }
        }
    }//¸ü¸ÄµØͼ´æ´¢·½Ê½
    BFS_Distance(mp,end,lg);//BFS¸üоàÀë
    BL_Mirror(Mirror,mp,lg,start,end);//±éÀú¸üд«Ëͺó¾àÀë 
    if(mp[start.first][start.second]==INT_MAX) return -1;
    BFS_ans(Mirror,mp,lg,start,end);//BFS»ñÈ¡´ð°¸
    
    /*cout<<"Mirror"<<endl;
    for(auto &i:Mirror)
    {
        for(auto &j:i)
        {
            printf("%02d ",j);
        }
        cout<<endl;
    }*/
    if(Mirror[end.first][end.second]==INT_MAX) return -1;
    else return Mirror[end.first][end.second];
}
int main()
{
    vector<string> maze;string s;
    while(cin>>s)
    {
        maze.push_back(s);
    }
    int ans=challengeOfTheKeeper(maze);
    cout<<ans<<endl;
    return 0;
}

限制:文章来源地址https://www.toymoban.com/news/detail-585668.html

  • 4 <= maze.length == maze[i].length <= 200
  • maze[i][j] 仅包含 ".""#""S""T"

到了这里,关于2023-07-18力扣今日二题-太难了吧的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 2023-07-25力扣今日二题-KMP

    链接: 28. 找出字符串中第一个匹配项的下标 题意: 求字符串s1中s2的最小下标 解: 字符串匹配板子题,来复习一下KMP,好久没写了,花了挺久才理清楚 基本思想这里不复习,主要复习写法 next[i] 表示当匹配第 i 个字符时匹配不上,需要退回到的位置,同时 next[i] 存储的是

    2024年02月15日
    浏览(60)
  • 2023-07-18力扣每日一题-有点难

    链接: 1851. 包含每个查询的最小区间 题意: 给定一个区间二维数组,有 N个[L,R] 区间(闭区间) 给定一组查询,有 M个正整数 ,求 存在于区间数组中的最小 R-L+1 满足 L=M[i]=R 解: 本来 看标签有个扫描线,想写个差分,然后排序查询整O(1)查询的,没写出来QWQ,也不知道有没

    2024年02月16日
    浏览(69)
  • 2023-08-07力扣今日五题

    链接: 剑指 Offer 53 - II. 0~n-1中缺失的数字 题意: 如题 解: 长度n的递增数组里,要找0到n中没出现的那个数字,那么出现的下标是0到n-1,一一对应即可,都出现了就是n没有 实际代码: 限制: 1 = 数组长度 = 10000 附记简单题 剑指 Offer 53 - I. 在排序数组中查找数字 I 0 = num

    2024年02月13日
    浏览(34)
  • 2023-07-15力扣今日四题

    链接: 1377. T 秒后青蛙的位置 题意: 一个n节点无向树,遍号1到n,青蛙从 顶点1 开始**(第0秒在顶点1)** 每过一秒: 青蛙 等概率 跳到 该节点的子节点 ,如果该节点没有子节点则原地不动 只跳子节点或者留在原地,即题目中的 不跳回访问过的节点 解: n才100,数据贼小,

    2024年02月16日
    浏览(39)
  • 2023-07-12力扣今日三题

    链接: 2058. 找出临界点之间的最小和最大距离 题意: 链表 某个节点 严格大于 前后时,这个节点为 局部极大值节点 ;某个节点 严格小于 前后时,这个节点为 局部极小值节点 前提:必须前后均非空 找两个不同临界点的 最大距离和最小距离 解: 一开始还以为要找极大和极

    2024年02月15日
    浏览(34)
  • 2023-08-07力扣今日七题-好题

    链接: 剑指 Offer 11. 旋转数组的最小数字 154. 寻找旋转排序数组中的最小值 II 题意: 找一个数组里的最小值,这个数组是有非递减数组旋转而来的,旋转n次表示把前n个数 移动 到数组末尾 解: 很有趣的二分,由于是非递减数组旋转而来,所以最小值往右一定小于等于最小

    2024年02月14日
    浏览(36)
  • 2023-08-07力扣今日六题-不错题

    链接: 剑指 Offer 04. 二维数组中的查找 题意: 一个二维矩阵数组,在行上非递减,列上也非递减 解: 虽然在行列上非递减,但是整体并不有序,第一行存在大于第二行的数字,第一列存在大于第二列的数字,所有非递减只对单行单列有效 如果从左上角开始遍历,就会发现

    2024年02月14日
    浏览(40)
  • 2023-09-07力扣每日一题

    链接: [2594. 修车的最少时间](https://leetcode.cn/problems/form-smallest-number-from-two-digit-arrays/) 题意: 一个能力R的人R*N*N分钟修N辆车,求最快多久修完(多人多车) 解: 二分很好想,主要是怎么检查(数学废物润去看题解了) 实际代码: 限制: 1 = ranks.length = 105 1 = ranks[i] = 100 1 = ca

    2024年02月09日
    浏览(39)
  • 2023-07-15力扣每日一题

    链接: 18. 四数之和 题意: 一个数组n,一个目标值t,在数组内找四个数字和等于t,求能有多少种组合 解: 0716:一看怎么昨天卡没打,原来昨天做的第一题不是每日一题,麻了 n很小,200,那么 先排序 ,然后弄一个 双指针开双循环 l,r ,确定每个组合的最大数字-数字4和最

    2024年02月16日
    浏览(40)
  • 2023-07-29力扣每日一题

    链接: 141. 环形链表 题意: 求链表是否有环 解: 刚好昨天做完的初级算法链表题,翻转和暴力 实际代码: 限制: 链表中节点的数目范围是 [0, 104] -105 = Node.val = 105 pos 为 -1 或者链表中的一个 有效索引 。

    2024年02月15日
    浏览(38)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包