Error message here!

Hide Error message here!

忘记密码?

Error message here!

请输入正确邮箱

Hide Error message here!

密码丢失?请输入您的电子邮件地址。您将收到一个重设密码链接。

Error message here!

返回登录

Close

高级数据结构详解

c1714-gzr 2020-08-16 22:49:00 阅读数:111 评论数:0 点赞数:0 收藏数:0

//本文同步发表于简书,若想食用更佳,点击查看原文:https://www.jianshu.com/p/978859c65c1b

前言

洛谷签到

高级数据结构难点很多,而且小编接近一年没有碰过代码了,简书一天能发布的文章数目有限,所以今天决定爆肝一个晚上来一个超长的博客。
但小编能力有限,只会讲解下列几个部分:

  • 树、图遍历的基础——搜索
  • 队列
  • 树的基本知识
  • 二叉树
  • 二叉排序树
  • 平衡树Treap
  • 红黑树(待更中……)
  • 树状数组
  • 线段树
  • 图论(待更中……)

实际上这都是我从网上找来的一大堆看似很高级,实则很高级的东西,但是小编会非常详细的记录经验和讲解知识,以及一些实际的例题。
不过图论内容较多,图论将会另更一篇(不过如果想立刻学的话可以看一下我昔日的博客:传送门),届时在章末补上链接。

一、树、图遍历的基础——搜索

在此部分,我们先讲解深度优先搜索(dfs),广度优先搜索就放到队列里面讲。
搜索是至关重要的,因为树,图在遍历时,使用的就是搜索算法,遍历是它们的基本操作之一。

1)前置基础

务必学会递归

2)核心思想

如果你现在正身处一个迷宫中,你想走出迷宫,那么方法主要有两种

  • 1>一条路走到黑,不撞南墙不回头,只要认定一个方向,就一直走到边界才掉头
    DFS

  • 2>环顾四周,不停向外扩展,先看离自己近的是不是出口,再看远的
    BFS
    第一种办法靠碰运气,说不准第一次方向就蒙对了,但也有可能运气差到遍历整个地图才能找到。
    第二种情况也靠碰运气,说不准终点就在起点旁边,但是也可能运气差到终点在边界处。
    我们现在将要讲解的就是第一种办法。

3)谈谈怎么代码实现吧

整个过程是这样的:

void dfs(一些需要传递的信息,来唯一识别当前的状态,例如当前走的次数,当前的位置等)
{
if(判断当前状态是否是目标状态) 如果是就存下这个答案,返回
for(逐个枚举可能的状态)
{
扩展新状态;
if(新状态可以使用)
{
有时需要做标记;
dfs(新状态);
回溯,即撤回标记,防止下次不能再到达这个状态(有时不需要回溯)
}
}
}

具体一点,对于迷宫,要求输出最小步数,可以修改成这样:

void dfs(横坐标,纵坐标,当前步数)
{
if(横坐标==终点横坐标&&纵坐标==终点纵坐标)
{
ans=min(ans,当前步数);
return;
}
for(枚举四个方向,即上下左右)
{
扩展出下一步的横坐标,纵坐标;
if(横坐标、纵坐标没有超出地图范围且这个新地方没有走过)
{
标记这个点走过了;
dfs(新横坐标,新纵坐标,步数+1);
标记这个点没有走过;
}
}
}

例题

例1

对于上面的迷宫,正好小编最近刷了一道规规矩矩的迷宫题。
题目链接:https://www.luogu.com.cn/problem/P1605
对于不想抬起宝贵的手点击链接(因为这样手移动会做功消耗动能,与空气摩擦还要生热)的同志,直接看题吧:

P1605 迷宫

题目背景
给定一个N*M方格的迷宫,迷宫里有T处障碍,障碍处不可通过。给定起点坐标和终点坐标,问: 每个方格最多经过1次,有多少种从起点坐标到终点坐标的方案。在迷宫中移动有上下左右四种方式,每次只能移动一个方格。数据保证起点上没有障碍。

题目描述

输入格式
第一行N、M和T,N为行,M为列,T为障碍总数。第二行起点坐标SX,SY,终点坐标FX,FY。接下来T行,每行为障碍点的坐标。

输出格式
给定起点坐标和终点坐标,问每个方格最多经过1次,从起点坐标到终点坐标的方案总数。

输入输出样例
输入 #1
2 2 1
1 1 2 2
1 2
输出 #1
1
说明/提示
【数据规模】

1≤N,M≤5

AC代码

#include<bits/stdc++.h>
using namespace std;
int n,m,t,ans,sx,sy,fx,fy,a,b;
int edge[100][100],mapp[100][100];
int next[4][2]={{1,0},{-1,0},{0,1},{0,-1}};//下一步怎么走
void dfs(int x,int y)
{
if(x==fx&&y==fy) //判断目标状态
{
ans++;//解的个数增加
return;
}
for(int i=0;i<4;i++)
{
int tx=x+next[i][0];
int ty=y+next[i][1];//扩展出下一步的位置
if(tx<1||ty<1||tx>n||ty>m||mapp[tx][ty]==1||edge[tx][ty]==1) continue; //判断下一步走这个点是否成立
mapp[tx][ty]=1;//标记走过了,防止同一路径重复走造成死循环
dfs(tx,ty);
mapp[tx][ty]=0;//标记回没走过,因为可能另一条路径需要经过这个点
}
}
int main()
{
cin>>n>>m>>t;
cin>>sx>>sy>>fx>>fy;
for(int i=1;i<=t;i++)
{
cin>>a>>b;
edge[a][b]=1;//标记障碍物
}
mapp[sx][sy]=1;
dfs(sx,sy);
cout<<ans;
return 0;
}

例2

题目链接:https://www.luogu.com.cn/problem/P1135

P1135 奇怪的电梯

预览结束,请点此进入原文:https://www.jianshu.com/p/978859c65c1b

版权声明
本文为[c1714-gzr]所创,转载请带上原文链接,感谢
https://www.cnblogs.com/TFLS-gzr/p/13514912.html

支付宝红包,每日可领(支付宝免费1-2元支付红包)