搜索+图论1 练习答案+思路

news/2025/2/8 18:14:17 标签: 深度优先, 算法

走迷宫


代码

#include<bits/stdc++.h>

using namespace std;

#define int long long

const int N=105;

int ans=0x3f3f3f3f;

struct node
{
    int x;
    int y;
    int step;
};

int n,m;

char g[N][N];
bool vis[N][N];

int dx[4]= {-1,1,0,0};
int dy[4]= {0,0,1,-1};

void bfs(int x,int y,int X,int Y)
{
    queue<node> q;

    q.push({x,y,0});

    while(!q.empty())
    {
        node t=q.front();

        if(t.x==X && t.y==Y)
        {
            ans=t.step;
            break;
        }

        q.pop();

        for(int i=0; i<4; i++)
        {
            int tx=t.x+dx[i];
            int ty=t.y+dy[i];

            if(tx<1 || ty<1 || tx>n || ty>m || g[tx][ty]=='0' || vis[tx][ty]) continue;

            vis[tx][ty]=true;
            q.push({tx,ty,t.step+1});

        }
    }

}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin>>n>>m;

    for(int i=1; i<=n; i++)
    {
        for(int j=1; j<=m; j++)
        {
            cin>>g[i][j];
        }
    }

    int x1,y1,x2,y2;

    cin>>x1>>y1>>x2>>y2;

    bfs(x1,y1,x2,y2);

    if(ans==0x3f3f3f3f)
    {
        cout<<"-1"<<endl;
    }
    else
    {
        cout<<ans<<endl;
    }

    return 0;
}

马走日

  注意dx和dy，因为马的跳跃方式比较特殊，所以要注意不要写错了

代码

#include<bits/stdc++.h>

using namespace std;

#define int long long

const int N=16;

int n,m,x,y;

int dx[8]={2,2,-2,-2,1,1,-1,-1};
int dy[8]={1,-1,1,-1,2,-2,2,-2};

bool vis[N][N];

int ans;

void dfs(int nx,int ny,int cnt)
{
    if(cnt==n*m)
    {
        ans++;
        return;
    }

    for(int i=0;i<8;i++)
    {
        int X=nx+dx[i];
        int Y=ny+dy[i];

        if(X<0 || Y<0 || X>=n || Y>=m || vis[X][Y]) continue;
        vis[X][Y]=true;
        dfs(X,Y,cnt+1);
        vis[X][Y]=false;
    }
}

void solve()
{
    memset(vis,false,sizeof(vis));
    ans=0;

    cin>>n>>m>>x>>y;

    vis[x][y]=true;
    dfs(x,y,1);

    cout<<ans<<endl;

}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    cin>>t;

    while(t--)
    {
        solve();
    }

    return 0;
}

奇怪的电梯

DFS代码

#include<bits/stdc++.h>

using namespace std;

#define int long long

const int N=205;

int K[N];
int dis[N];
int n,A,B;

void dfs(int now,int step)
{
    dis[now]=step;

    int up=now+K[now];
    if(up<=n && step+1<dis[up]) dfs(up,step+1);

    int down=now-K[now];
    if(down>=1 && step+1<dis[down]) dfs(down,step+1);
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin>>n>>A>>B;

    for(int i=1;i<=n;i++)
    {
        cin>>K[i];
    }

    for(int i=1;i<=n;i++)
    {
        dis[i]=0x3f3f3f3f;
    }

    dfs(A,0);

    if(dis[B]==0x3f3f3f3f)
    {
        cout<<"-1"<<endl;
    }
    else
    {
        cout<<dis[B]<<endl;
    }

    return 0;
}


BFS代码
 

#include<bits/stdc++.h>

using namespace std;

#define int long long

const int N=205;

int n,A,B;

int K[N];
bool vis[N];

int ans=-1;

void bfs()
{
    queue<pair<int,int>> q;
    q.push({A,0});
    vis[A]=true;

    while(!q.empty())
    {
        pair<int,int> t=q.front();
        q.pop();

        int now=t.first;
        int step=t.second;

        if(now==B)
        {
            ans=step;
            break;
        }

        int up=now+K[now];

        if(!vis[up] && up<=n)
        {
            vis[up]=true;
            q.push({up,step+1});
        }

        int down=now-K[now];

        if(!vis[down] && down>=1)
        {
            vis[down]=true;
            q.push({down,step+1});
        }

    }
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin>>n>>A>>B;

    for(int i=1; i<=n; i++)
    {
        cin>>K[i];
    }

    bfs();

    cout<<ans<<endl;

    return 0;
}

The Lakes

思路

典型的连通块问题，模板题

代码

#include<bits/stdc++.h>

using namespace std;

#define int long long

const int N=1005;

int dx[4]={-1,1,0,0};
int dy[4]={0,0,-1,1};

int n,m;

int ans;

int a[N][N];
bool vis[N][N];

int cnt=0;

void dfs(int x,int y)
{
    cnt+=a[x][y];

    for(int i=0;i<4;i++)
    {
        int X=x+dx[i];
        int Y=y+dy[i];

        if(X<1 || Y<1 || X>n || Y>m || vis[X][Y] || a[X][Y]==0) continue;

        vis[X][Y]=true;
        dfs(X,Y);
    }
}

void solve()
{
    cin>>n>>m;

    ans=0;

    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            vis[i][j]=false;
        }
    }

    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            cin>>a[i][j];
        }
    }

    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            if(!vis[i][j] && a[i][j]!=0)
            {
                cnt=0;
                vis[i][j]=true;
                dfs(i,j);
                ans=max(ans,cnt);
            }
        }
    }

    cout<<ans<<endl;
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    cin>>t;

    while(t--)
    {
        solve();
    }

    return 0;
}

Robot Factory

思路

有一定的技巧性，读懂题意很重要，这道题的题意有些难以理解，包含位运算的知识

问题 3744 - YTUOJ 课下可以练习

代码

#include<bits/stdc++.h>

using namespace std;

#define int long long

const int N=1005;

int n,m;

int g[N][N];
bool vis[N][N];

int cnt=0;

vector<int> ans;

void dfs(int x,int y)
{
    cnt++;

    if((g[x][y]&8)==0 && x-1>=1 && !vis[x-1][y])
    {
        vis[x-1][y]=true;
        dfs(x-1,y);
    }

    if((g[x][y]&4)==0 && y+1<=m && !vis[x][y+1])
    {
        vis[x][y+1]=true;
        dfs(x,y+1);
    }

    if((g[x][y]&2)==0 && x+1<=n && !vis[x+1][y])
    {
        vis[x+1][y]=true;
        dfs(x+1,y);
    }

    if((g[x][y]&1)==0 && y-1>=1 && !vis[x][y-1])
    {
        vis[x][y-1]=true;
        dfs(x,y-1);
    }
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin>>n>>m;

    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            cin>>g[i][j];
        }
    }

    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            if(!vis[i][j])
            {
                vis[i][j]=true;
                cnt=0;
                dfs(i,j);
                ans.push_back(cnt);
            }
        }
    }

    sort(ans.begin(),ans.end(),greater<>());

    for(int i=0;i<ans.size();i++)
    {
        cout<<ans[i]<<" ";
    }


    return 0;
}

King Escape

思路

是八皇后问题的简化版，建议可以先去学习八皇后问题
843. n-皇后问题 - AcWing题库
注意防止数组越界即可

代码

#include<bits/stdc++.h>

using namespace std;

#define int long long

const int N=1005;

int n;

bool row[N],col[N],dig[2*N],udig[2*N],vis[N][N];

pair<int,int> a,b,c;

int dx[8]={-1,-1,-1,1,1,1,0,0};
int dy[8]={-1,0,1,-1,0,1,-1,1};

bool f=false;

void dfs(int x,int y)
{
    if(x==c.first && y==c.second)
    {
        f=true;
    }

    for(int i=0;i<8;i++)
    {
        int X=x+dx[i];
        int Y=y+dy[i];

        if(!row[X] && !col[Y] && !dig[X+Y] && !udig[X-Y+n] && !vis[X][Y] && X>=1 && X<=n && Y>=1 && Y<=n)
        {
            vis[X][Y]=true;
            dfs(X,Y);
        }
    }
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin>>n;

    cin>>a.first>>a.second;
    cin>>b.first>>b.second;
    cin>>c.first>>c.second;

    row[a.first]=true;
    col[a.second]=true;
    dig[a.first+a.second]=true;
    udig[a.first-a.second+n]=true;

    dfs(b.first,b.second);

    if(f==true)
    {
        cout<<"YES"<<endl;
    }
    else
    {
        cout<<"NO"<<endl;
    }


    return 0;
}

Hidden Weights

思路

图的遍历，学会基本的建图，以及图的遍历即可，再加上对于题意的理解，即可

代码 

#include<bits/stdc++.h>

using namespace std;

#define int long long

const int N=200010;

bool vis[N];
int dis[N];
vector<pair<int,int>> e[N];

void dfs(int u)
{
    for(auto v:e[u])
    {
        if(!vis[v.first])
        {
            vis[v.first]=true;
            dis[v.first]=dis[u]-v.second;
            dfs(v.first);
        }
    }
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n,m;
    cin>>n>>m;

    for(int i=1;i<=m;i++)
    {
        int u,v,w;
        cin>>u>>v>>w;
        e[v].push_back({u,w});
        e[u].push_back({v,-w});
    }

    for(int i=1;i<=n;i++)
    {
        if(!vis[i])
        {
            vis[i]=true;
            dfs(i);
        }
    }

    for(int i=1;i<=n;i++)
    {
        cout<<dis[i]<<" \n"[i==n];
    }

    return 0;
}

共享单车

思路

YTU 3166 共享单车 DFS 记忆化搜索-CSDN博客

代码 

#include<bits/stdc++.h>

using namespace std;

#define int long long

const int N=1005;

int n,m;

char g[N][N];
int dis[N][N];

int ans=0x3f3f3f3f;

void dfs(int x,int y)
{
    if(g[x][y]=='x')
    {
        ans=min(ans,dis[x][y]);
    }

    if(x+1<=n && g[x+1][y]!='*' && dis[x][y]+100 < dis[x+1][y] )//向南
    {
        dis[x+1][y]=dis[x][y]+100;
        dfs(x+1,y);
    }

    if(x-1>=1 && g[x-1][y]!='*' && dis[x][y]+100< dis[x-1][y] )//向北
    {
        dis[x-1][y]=dis[x][y]+100;
        dfs(x-1,y);
    }

    if(y+1<=m && g[x][y+1]!='*' && dis[x][y]+100< dis[x][y+1])//向东
    {
        dis[x][y+1]=dis[x][y]+100;
        dfs(x,y+1);
    }

    if(y-1>=1 && g[x][y-1]!='*' && dis[x][y]+100< dis[x][y-1])//向西
    {
        dis[x][y-1]=dis[x][y]+100;
        dfs(x,y-1);
    }

    if(x+1<=n && y+1<=m && g[x+1][y+1]!='*' && dis[x][y]+141<dis[x+1][y+1])//向东南
    {
        dis[x+1][y+1]=dis[x][y]+141;
        dfs(x+1,y+1);
    }

    if(x+1<=n && y-1>=1 && g[x+1][y-1]!='*' && dis[x][y]+141<dis[x+1][y-1] )//向西南
    {
        dis[x+1][y-1]=dis[x][y]+141;
        dfs(x+1,y-1);
    }

    if(x-1>=1 && y+1<=m && g[x-1][y+1]!='*' && dis[x][y]+141<dis[x-1][y+1] )//向东北
    {
        dis[x-1][y+1]=dis[x][y]+141;
        dfs(x-1,y+1);
    }

    if(x-1>=1  && y-1>=1 && g[x-1][y-1]!='*' && dis[x][y]+141< dis[x-1][y-1])//向西北
    {
        dis[x-1][y-1]=dis[x][y]+141;
        dfs(x-1,y-1);
    }

}

void solve()
{
    cin>>n>>m;

    ans=0x3f3f3f3f;

    for(int i=1; i<=n; i++)
    {
        for(int j=1; j<=m; j++)
        {
            cin>>g[i][j];
        }
    }

    memset(dis,0x3f,sizeof(dis));

    for(int i=1; i<=n; i++)
    {
        for(int j=1; j<=m; j++)
        {
            if(g[i][j]=='o')
            {
                dis[i][j]=0;
                dfs(i,j);
            }
        }
    }

    if(ans==0x3f3f3f3f)
    {
        cout<<"-1"<<endl;
    }
    else
    {
        cout<<ans<<endl;
    }

}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    cin>>t;

    while(t--)
    {
        solve();
    }

    return 0;
}

图的存储

代码

#include<bits/stdc++.h>

using namespace std;

#define int long long

const int N=1005;

int g[N][N];
vector<int> adj[N];

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n,m;
    cin>>n>>m;

    for(int i=1;i<=m;i++)
    {
        int u,v;
        cin>>u>>v;

        g[u][v]=1;
        g[v][u]=1;

        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            cout<<g[i][j]<<" ";
        }
        cout<<endl;
    }

    for(int i=1;i<=n;i++)
    {
        cout<<adj[i].size()<<" ";

        sort(adj[i].begin(),adj[i].end());

        for(auto x:adj[i])
        {
            cout<<x<<" ";
        }
        cout<<endl;
    }



    return 0;
}

图的遍历

思路

反向建边+dfs，这道题问的是从某个点出发，所能达到的最大的节点，那么不如转化思维，改为，从最大的节点开始进行操作，看看最大的节点可以被哪些节点所到达，那么哪些节点的答案一定是最大节点，从而被标记为不可更新，所以，从n到1进行dfs遍历，就可以得出答案

代码 

#include<bits/stdc++.h>

using namespace std;

#define int long long

const int N=100005;

vector<int> e[N];
bool vis[N];
int A[N];

void dfs(int u,int x)
{
    for(auto v:e[u])
    {
        if(!vis[v])
        {
            vis[v]=true;
            A[v]=x;
            dfs(v,x);
        }
    }
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n,m;
    cin>>n>>m;

    for(int i=1;i<=n;i++)
    {
        A[i]=i;
    }

    for(int i=1;i<=m;i++)
    {
        int u,v;
        cin>>u>>v;

        e[v].push_back(u);
    }

    for(int i=n;i>=1;i--)
    {
        if(!vis[i])
        {
            vis[i]=true;
            dfs(i,i);
        }
    }

    for(int i=1;i<=n;i++)
    {
        cout<<A[i]<<" \n"[i==n];
    }


    return 0;
}


http://www.niftyadmin.cn/n/5845187.html

相关文章

【模型部署】大模型部署工具对比：SGLang, Ollama, VLLM, LLaMA.cpp如何选择？

【模型部署】大模型部署工具对比：SGLang, Ollama, VLLM, LLaMA.cpp如何选择？

在选择大模型部署工具时&#xff0c;需要考虑多个因素&#xff0c;包括性能、支持的语言和模型、硬件支持、易用性以及社区支持等。以下是对比分析&#xff1a; 性能 VLLM (Virtual Tensor Language): VLLM 是一个高性能的推理库&#xff0c;特别适用于长序列任务。它通过虚…
阅读更多...
FPGA实现SDI视频解码转UltraScale GTH光口传输，基于GS2971+Aurora 8b/10b编解码架构，提供2套工程源码和技术支持

FPGA实现SDI视频解码转UltraScale GTH光口传输，基于GS2971+Aurora 8b/10b编解码架构，提供2套工程源码和技术支持

目录 1、前言工程概述免责声明 2、相关方案推荐我已有的所有工程源码总目录----方便你快速找到自己喜欢的项目我这里已有的 GT 高速接口解决方案本博已有的 SDI 编解码方案 3、工程详细设计方案工程设计原理框图SDI 输入设备GS2971芯片BT1120转RGB视频数据组包基于UltraScale G…
阅读更多...
RTMP 和 WebRTC

RTMP 和 WebRTC

WebRTC（Web Real-Time Communication）和 RTMP（Real-Time Messaging Protocol）是两种完全不同的流媒体协议，设计目标、协议栈、交互流程和应用场景均有显著差异。以下是两者的详细对比，涵盖协议字段、交互流程及核心设计思想。 一、协议栈与设计目标对比 特性RTMPWebRTC传…
阅读更多...
kubeadm构建k8s源码阅读环境

kubeadm构建k8s源码阅读环境

目标 前面看了minikube的源码了解到其本质是调用了kubeadm来启动k8s集群&#xff0c;并没有达到最初看代码的目的。 所以继续看看kubeadm的代码&#xff0c;看看能否用来方便地构建源码调试环境。 k8s源码编译 kubeadm源码在k8s源码库中&#xff0c;所以要先克隆k8s源码。之…
阅读更多...
Node.js中http模块（二）

Node.js中http模块（二）

一、http模块 http 模块是 Node.js 官方提供的、用来创建 web 服务器的模块。通过 http 模块提供的 http.createServer0) 方法&#xff0c;就能方便的把一台普通的电脑&#xff0c;变成一台 Web 服务器&#xff0c;从而对外提供 Web 资源服务。 二、域名和域名服务器 尽管 I…
阅读更多...
git SourceTree 使用

git SourceTree 使用

Source Tree 使用原理 文件的状态 创建仓库和提交 验证 再克隆的时候发发现一个问题&#xff0c;就是有一个 这个验证&#xff0c;起始很简单 就是 gitee 的账号和密码&#xff0c;但是要搞清楚的是账号不是名称&#xff0c;我之前一直再使用名称登录老是出问题 这个很简单的…
阅读更多...
位置定位与IP属地：异同解析与实际应用

位置定位与IP属地：异同解析与实际应用

在数字化和网络化的今天&#xff0c;位置定位和IP属地已成为我们日常生活中不可或缺的两个概念。那么&#xff0c;位置定位和IP属地是不是一样的&#xff1f;‌虽然都涉及到地理位置的识别&#xff0c;实则在定义、应用场景及精确度上存在着显著差异。本文旨在深入探讨位置定位…
阅读更多...
确保数据一致性：RabbitMQ 消息传递中的丢失与重复问题详解

确保数据一致性：RabbitMQ 消息传递中的丢失与重复问题详解

前言 RabbitMQ 是一个常用的消息队列工具&#xff0c;虽然它能帮助高并发环境下实现高效协同&#xff0c;但我们也曾遇到过因网络波动、确认机制失效、系统故障和代码异常等原因导致消息丢失或重复消费的问题&#xff0c;本文将探讨原因及解决方案&#xff0c;希望能为大家提供…
阅读更多...
最新文章

Copyright @ 2022~2023