蓝桥杯算法心得——仙界诅咒(dfs)

这篇具有很好参考价值的文章主要介绍了蓝桥杯算法心得——仙界诅咒(dfs)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

大家好,我是晴天学长,搜索型的dfs,差点开二维矩阵了,仔细一想,没那么夸张啊,哈哈哈,需要的小伙伴可以关注支持一下哦!后续会继续更新的。💪💪💪


1) .仙界诅咒

蓝桥杯算法心得——仙界诅咒(dfs),算法,深度优先,算法,蓝桥杯
仙境诅咒

问题描述

在一片神秘的仙境中,有N位修仙者,他们各自在仙境中独立修炼,拥有自己独特的修炼之道和修炼之地,修仙者们彼此之间相互尊重、和谐相处。

然而,有一天,仙境的主宰者妮妮(第一位修仙者)受到了诅咒,该诅咒会向距离妮妮不超过D的范围内的修仙者传播。也就是说,如果一个修仙者被诅咒,那么在距离他不超过D的范围内的所有修仙者都会被诅咒。

现在,你需要预测哪些修仙者最终会被诅咒,以便及时采取措施,保护仙境的和平与安宁。

输入格式

第—行输入一个正整数N(1 <N<.103),表示仙境中有Ⅳ位修仙者。

接下来N行,每行两个实数X;和Y(-103<X;,Y <103 ),表示第à位修仙者的坐标(X;,Y)。第一位修仙者即仙境的主宰者妮妮。

最后一行输入一个正整数D(1<D<103),表示诅咒传播的范围。

输出格式

输出N行,每行一个整数,第i行的整数为1表示第i位修仙者最终被诅咒,为0则表示第i位修仙者没有被诅咒。
样例输入
5
0 0
1 1
0 1
1 0
2 2
1
样例输出
1
1
1
1
0


2) .算法思路

仙境诅咒

1.接收数据
2.循环数据,看与自己的直线距离是否满足D


3).算法步骤

1.导入所需的Java I/O类和其他类。

2.声明静态变量和列表。

3.创建BufferedReader对象和PrintWriter对象,用于输入和输出。

4.读取输入的行,并解析为整数N(表示点的数量)。

5.创建布尔数组st,用于标记每个点是否被传播到。

6.使用循环读取每个点的坐标,并将其添加到xiuxian列表中。

7.读取输入的行,并解析为整数D(表示传播的最大距离)。

8.调用dfs方法开始传播,传入起始点的索引0、点的数量N、布尔数组st和最大传播距离D。

9.在dfs方法中,将当前点标记为已传播(st[i] = true)。

10.获取当前点的坐标s1。

11.遍历所有点的索引k。

12.检查点k是否未被传播(!st[k])。

13.获取点k的坐标s2。

14.计算当前点到点k的距离distance,使用欧几里得距离公式。

15.如果距离小于等于最大传播距离D,递归调用dfs方法,传入点k的索引、点的数量N、布尔数组st和最大传播距离D。

16.在dfs方法结束后,返回上一层递归。

17.在主方法中,遍历所有点的索引i。

18.如果点i被传播到(st[i] = true),输出1;否则,输出0。

19.刷新输出流,并关闭PrintWriter对象。


4). 代码实例

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.List;

public class Main {
    static BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
    static PrintWriter out = new PrintWriter(new PrintWriter(System.out));
    static String[] lines;
    static List<double[]> xiuxian = new ArrayList<>();


    public static void main(String[] args) throws IOException {
        lines = in.readLine().split(" ");
        int N = Integer.parseInt(lines[0]);
        boolean[] st = new boolean[N];
        for (int i = 0; i < N; i++) {
            lines = in.readLine().split(" ");
            double x = Double.parseDouble(lines[0]);
            double y = Double.parseDouble(lines[1]);
            xiuxian.add(new double[]{x, y});
        }
        lines = in.readLine().split(" ");
        int D = Integer.parseInt(lines[0]);

        // 开始传播
        dfs(0,N,st,D);
        for (int i = 0; i < N; i++) {
            if (st[i])out.println(1);
            else out.println(0);
        }
        out.flush();
        out.close();
    }

    private static void dfs(int i, int N, boolean[] st, int D) {
        st[i] = true;
        double[] s1 = xiuxian.get(i);

        for (int k = 0; k < N; k++) {
            if (!st[k]){
                double[] s2 = xiuxian.get(k);
                double distance = Math.sqrt((s2[0] - s1[0]) * (s2[0] - s1[0]) + (s2[1] - s1[1]) * (s2[1] - s1[1]));
                if (distance <= D) {
                    dfs(k,N,st,D);
                }
            }
        }
    }
}


4).总结

  • 对于时间复杂度的判断。

试题链接:文章来源地址https://www.toymoban.com/news/detail-756820.html

到了这里,关于蓝桥杯算法心得——仙界诅咒(dfs)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

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

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

相关文章

  • 【洛谷刷题】蓝桥杯专题突破-深度优先搜索-dfs(4)

    目录 写在前面: 题目:P1149 [NOIP2008 提高组] 火柴棒等式 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn) 题目描述: 输入格式: 输出格式: 输入样例: 输出样例: 解题思路: 代码: AC !!!!!!!!!! 写在最后: 怎么样才能学好一个算法? 我个人认为,系统性的刷题尤

    2023年04月08日
    浏览(45)
  • 【洛谷刷题】蓝桥杯专题突破-深度优先搜索-dfs(1)

    目录 写在前面: 题目:P1036 [NOIP2002 普及组] 选数 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn) 题目描述: 输入格式: 输出格式: 输入样例: 输出样例: 解题思路: 代码: AC !!!!!!!!!! 写在最后: 怎么样才能学好一个算法? 我个人认为,系统性的刷题尤为重要

    2024年01月23日
    浏览(39)
  • 【蓝桥杯Java组】用Java带你暴走迷宫—DFS深度优先搜索

    📖📖 走迷宫 一类的问题一般都是暴力搜索解决,搜索的方法有两种:深度优先(DFS)和广度优先(BFS),而提到DFS就离不开递归,涉及到递归的问题理解起来还是有难度的,代码编写不当很容易造成栈溢出。 🌻🌻今天就用三道 走迷宫 问题带你彻底搞懂怎么用DFS秒杀迷宫

    2023年04月11日
    浏览(36)
  • 深度优先搜索(DFS)算法

    目录 算法思想 时间复杂度和空间复杂度 算法实现 算法优缺点 应用领域 深度优先搜索(DFS)算法的思想是从图的某个起始顶点开始,沿着一条路径尽可能深入地访问图中的所有顶点,直到不能继续为止,然后返回并探索其他路径。具体而言,DFS算法使用栈数据结构来实现,

    2024年02月05日
    浏览(45)
  • 【算法详解 | DFS算法】深度优先搜索解走迷宫问题 | 深度优先图遍历

    by.Qin3Yu 本文需要读者掌握 结构体 和 栈 的操作基础,完整代码将在文章末尾展示。 特别声明:本文为了尽可能使用简单描述,以求简单明了,可能部分专有名词定义不准确。 栈相关操作可以参考我的往期博文: 【C++数据结构 | 栈速通】使用栈完成十进制数转二四八进制数

    2024年02月03日
    浏览(49)
  • 深度优先搜索(DFS)(算法笔记)

    本文内容基于《算法笔记》和官方配套练题网站“晴问算法”,是我作为小白的学习记录,如有错误还请体谅,可以留下您的宝贵意见,不胜感激。 深度优先搜索是一种枚举所有完整路径以遍历所有情况的搜索方法,总是以“深度”作为前进的。实现方式是有很多,最

    2024年02月08日
    浏览(50)
  • [算法日志]图论: 深度优先搜索(DFS)

    ​ 深度优先搜索算法是一种遍历图这种数据结构的算法策略,其中心思想是朝图节点的一个方向不断跳转,当该节点无下一个节点或所有方向都遍历完时,便回溯朝上一个节点的另一个方向继续遍历。这种搜索策略与回溯法有异曲同工之妙。 正因为和回溯法有相似之处,所

    2024年02月03日
    浏览(62)
  • 【数据结构与算法】图遍历算法 ( 深度优先搜索 DFS | 深度优先搜索和广度优先搜索 | 深度优先搜索基本思想 | 深度优先搜索算法步骤 | 深度优先搜索理论示例 )

    图 的 遍历 就是 对 图 中的 结点 进行遍历 , 遍历 结点 有如下两种策略 : 深度优先搜索 DFS 广度优先搜索 BFS \\\" 深度优先搜索 \\\" 英文名称是 Depth First Search , 简称 DFS ; DFS 基本思想 : 访问第一个邻接结点 : 从 起始点 出发 , 该 起始点 可能有 若干 邻接结点 , 访问 第一个 邻接结点

    2024年02月02日
    浏览(46)
  • 图的遍历(搜索)算法(深度优先算法DFS和广度优先算法BFS)

    从图的某个顶点出发访问遍图中所有顶点,且每个顶点仅被访问一次。(连通图与非连通图) 1、访问指定的起始顶点; 2、若当前访问的顶点的邻接顶点有未被访问的,则任选一个访问之;反之,退回到最近访问过的顶点;直到与起始顶点相通的全部顶点都访问完毕; 3、若

    2024年01月17日
    浏览(46)
  • 第一周算法训练(dfs)(深度优先搜索算法)

    dfs: 深度优先搜索算法 ,是一种用于遍历或 搜索树或图的算法 .沿着树的深度遍历树的节点,尽可能深的搜索树的分支。当节点v的所在边都己被探寻过,搜索将回溯到发现节点v的那条边的起始节点。这一过程一直进行到已发现从源节点可达的所有节点为止。如果还存在未被

    2024年02月20日
    浏览(49)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包