2024/1/18 DFS BFS

目录

奇怪的电梯

马的遍历

PERKET（个人认为很抽象）

---

奇怪的电梯

P1135 奇怪的电梯 – 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

思路，还是用的bfs，建立一个结构体类型的队列，一个存当前的电梯层数，一个存当前走的步数

还要建一个bool类型的数组标记当前电梯层数是否走过

完整代码

#include 
const int N = 210;
int n,a,b;
int g[N];
int ans;
bool vis[N]{};
struct node
{
    int lou;
    int step;
};
void bfs()
{
    std::queue q;
    q.push({a,0});
    while(!q.empty())
    {
        node tmp=q.front();
        q.pop();
        int cur_low=tmp.lou,cur_step=tmp.step;
        if(cur_low==b)
        {
            std::cout=1&&vis[cur_low-g[cur_low]]==false)
        {
            q.push({cur_low-g[cur_low],cur_step+1});
            vis[cur_low-g[cur_low]]=true;
        }
    }
    std::cout> n >> a >> b;
    for(int i = 1;i > g[i];
    }
    bfs();
    return 0;
}

马的遍历

P1443 马的遍历 – 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

思路：用bfs，八个坐标，依次遍历 ，没有搜索到的点就输出-1

超时代码：

#include 
const int N = 410;
int n,m,x,y;
int g[N][N];
bool vis[N][N]{};
int rr[10]={-1,-2,-2,-1,1,2,2,1};
int cc[10]={-2,-1,1,2,2,1,-1,-2};
struct node
{
    int r,c,step;
};
void bfs(int ii,int jj)
{
    std::queue q;
    q.push({x,y,0});
    memset(vis,false,sizeof(vis));
    while(!q.empty())
    {
        node tmp=q.front();
        q.pop()服务器托管网;
        int cur_r=tmp.r,cur_c=tmp.c,cur_step=tmp.step;
        if(cur_r==ii&&cur_c==jj)
        {
            std::cout=1&&next_r=1&&next_c> n >> m >> x >> y;
    for(int i = 1;i 

因为每次都要进一次bfs，所以时间复杂度就提高了

所以只需要进一次bfs,用一个二维数组记录到达每个点的步数（因为要走下一个点必然会经过当前这个点）

ac代码

#include 
const int N = 410;
int n,m,x,y;
int g[N][N];
bool vis[N][N]{};
int rr[10]={-1,-2,-2,-1,1,2,2,1};
int cc服务器托管网[10]={-2,-1,1,2,2,1,-1,-2};
int ans[N][N];
struct node
{
    int r,c,step;
};
void bfs()
{
    memset(ans,-1,sizeof(ans));
    std::queue q;
    q.push({x,y,0});
    memset(vis,false,sizeof(vis));
    vis[x][y]=true;
    while(!q.empty())
    {
        node tmp=q.front();
        q.pop();
        int cur_r=tmp.r,cur_c=tmp.c,cur_step=tmp.step;
        ans[cur_r][cur_c]=cur_step;
        for(int i = 0;i =1&&next_r=1&&next_c> n >> m >> x >> y;
    bfs();
    for(int i = 1;i 

PERKET（个人认为很抽象）

P2036 [COCI 2008/2009 #2] PERKET – 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

思路：这道题用dfs，枚举选和不选两种状态，取最小值

完整代码

#include 
const int N = 15;
int a[N],b[N];
int n,ans=999999999;
void dfs(int i,int x,int y)//编号，酸度，甜度
{
    if(i>n)
    {
        if(x==1&&y==0)
            return;
        ans=std::min(std::abs(x-y),ans);
        return;
    }
    dfs(i+1,x*a[i],y+b[i]);
    dfs(i+1,x,y);
}
int main()
{
    std::cin >> n;
    for(int i = 1;i > a[i] >> b[i];
    }
    dfs(1,1,0);
    std::cout

服务器托管，北京服务器托管，服务器租用 http://www.fwqtg.net

相关推荐: W-TinyLFU 算法实现

前言 不同于服务器托管网常见的 LRU 或 LFU，Window TinyLFU 是一种非常高效的缓存设计方案。先来看下 LRU 和 LFU 算法的缺点： LFU 缺点： 需要为每个记录项维护频率信息，这将消耗大量的内存空间 可能存在旧数据长期不被淘汰（一开始…